기저사례1 백준 1629/c++ )) 곱셈 - divde and conquer, 재귀함수 그대로 주는대로 계산하면 연산시간이 너무 길어서 시간 초과하는 문제이다 재귀 함수로 분할정복 divde and conquer를 사용하여 연산 수를 줄이고, 각 입력의 최대값이 int 의 최대치 값 이므로 long long 을 사용하여 결과값의 오버플로우를 1차로 막는다 분할한 값을 합칠때 큰 수끼리의 곱셈을 해야하므로 long long 뿐 아니라 %c 로 모듈러 연산을 해줘서 2차로 오버플로우를 막아야 하는 문제이다 재귀함수라지만 내가 gr로 작성한 부분이 gr=gr*gr 이고 gr=gr*a%c 이라는 부분에서 왜인지 이해하느라 머리가 터졌고 시간도 몇시간을 걸려서 이해했지만, 이해했으니 비슷한 유형도 이제 익숙해질것이다 내일을 공부를 위해 더 늦기전에 자자... #include using namespa.. 2022. 6. 17. 이전 1 다음