1629번 곱셈(재귀, 분할정복) - ☆
#문제링크 : https://www.acmicpc.net/problem/1629
<전략>
1. A, B, C 모두 최대 2^32 정도까지 값을 가지기 때문에, 일반적인 반복문으로 해결하면 시간초과가 된다.
2. 메모이제이션으로 해결해보려해도, C값이 너무 크면, 메모리초과가 날 상황이 생긴다.
3. 세 수 모두 최대 2^32 정도까지라는 부분에 집중해보면, 시간초과가 나는 부분은 B가 2^32일때 문제가 된다. B번 반복해야하기 때문. 이 문제를 재귀 분할로 생각해보면, A=3이라 하면, 구하려는 값은 3^2^32의 모듈러다. 루트 분해 했을때, 3^(2^31 + 2^31)이 되고, 마찬가지로 2^30도 2^29, 2^29, 2^29은 2^28, 2^28 ... 으로 나타낼 수 있다. 즉, log(B)번만 반복하면 해당 문제를 풀 수가 있는 것이다. 아래는 처음 생각한 방식의 코드다.
※주의사항
1. 거듭제곱에서 지수를 이용해 반복횟수를 줄일 수 있는 방법을 생각해본다.
2. B가 짝수, 홀수일 경우를 나누어 해결해야 한다.
위 코드는 재귀를 호출하면 할수록 두갈래로 분기되어 들어간다. 즉, y값이 2^32로 시작할 경우, 끝값은 2^1 이겠지만, 이때 리프노드는 2^31개가 생성된다. 한마디로, 메모리초과, 시간초과가 모두 걸린다. 하지만, 위 코드는 맞는다고 뜬다. 그 이유는 컴파일러가 if(y%2==0)조건에서 같은 pow함수를 호출하는데, 이때, 두 값은 같다고 보고 재귀로 안들어간 후 넘어가는 것 같다. 즉, 컴파일러 자체적인 메모이제이션 효과로 통과가 되는 것으로 생각된다.
하지만, 엄연히 위 코드는 틀린 코드다. 재귀마다 분기하는 것은, 시간, 메모리 모두 엄청난 자원을 소모하게 된다.
<전략>
1. 재귀를 분기하지 않고, 다음 뎁스에서 넘어오는 리턴값을 변수에 저장하고 변수를 넘긴다. 이렇게 하면 재귀호출을 분기하지 않고 한번의 호출로도 원하는 값을 저장하고 넘길 수 있다.
※주의사항
1. y가 1일 경우, return x; 해버리면, x값이 그대로 출력되기 때문에, x%c를 리턴해주어야 한다. 나머지 연산을 불필요한 곳에서 제거하려다 보니 종료조건에서 불필요하다 생각해버려서 빼버렸던게 실수였다. y가 1일때도 생각해서 x%c를 반환해야 한다.
2. 홀수, 짝수일 경우를 나누어야 하고, 홀수일 때는 확실히 거듭제곱 논리에 맞게 코드를 작성해야한다.
