[백준] 13171번 A c++

1. 재귀 이용 큰 수에서부터 작은 수로 가는 방법 작은 수를 구해버린다 8제곱이면 4제곱 * 4제곱 4제곱 = 2제곱 * 2제곱 이런 식으로 구해주는 방법 이때 y가 짝수 면 그냥 곱하면 되고 홀수 면 A까지 한 번 더 구해준다. dp를 쓸까 하다가 배열의 크기가 너무 커서 할 수 없다고 판단했다. res(A % MOD, X)로 결괏값을 해주는 이유는 결국 A도 곱해야 되기에 이것도 곱하는 거니 % MOD 해준다. 2. dp + for 문 이용 dp는 문제에서 64번 반복하면 된다고 하니 dp[i]는 A^(2^i)의 값이라고 생각해서 구해줬다. 홀짝 나눠줄 필요가 없는 게 1 2 4 8 16.. 이므로 무조건 짝수만 구하면 되니까 나눌 필요 없다. 문제에서 11 = 1 + 2 + 8이..........

원문링크 : [백준] 13171번 A c++