정말 어렵다. 문제만 보면 이게 왜 실버1의 난이도인지 싶었다. 시간제한을 보고 살짝 쫄렸긴 했지만 과감하게 문제를 풀어보았다.
첫번째의 발견과 코드
- long long
우선 숫자의 제곱이다. B의 범위가 정말 중요하다. B의 제한이 없기 때문에 숫자는 매우 커질 것이라는 것을 염두에 두었고 그래서 int 대신에 long long을 사용했다.
-나머지 구하기
숫자를 다 제곱해서 마지막에 나머지 연산을 한다... 이것은 그렇다면 A^B를 한 값을 메모리에 저장한다는 의미이다. 그 값이 정말 무한히 클텐데 그 메모리를 저장할 만한 메모리 공간이 없을 것이다.
그렇다면 무엇을 생각해보아야 할까. 곱셈을 하고 나머지를 구한 것은 다른 의미로 고민을 해본다면 각 피연산자를 먼저 C로 나눈 나머지를 구하고 그 나머지를 계속 해서 곱하고 최종적으로 C로 나눈다고 생각해도 나쁘지 않다. 예를 들면 10을 10번 곱해서 3으로 나눈다는 것은 10을 먼저 3으로 나눈 나머지 값을 10번 곱해서 그 값을 최종적으로 3으로 다시 나눈 나머지를 구해 메모리 용량을 줄여보겠다는 다짐이었다.
그렇게 작성한 코드는 다음과 같다.
int main()
{
long long A, B, C;
long long result = 1;
cin >> A >> B >> C;
for(int i=0; i<B; i++)
{
result = result * (A % C);
}
cout << result % C << "\n";
}하지만 가차없이 실패가 떴다. 이러면 괜히 실버1의 문제가 아니겠지... 무엇이 과연 문제인지 한번 고민해보았다.
두번째 발견과 코드
- 재귀함수와 시간복잡도 고려
같이 문제를 풀어본 친구한테 물어보았다. 우선 공간복잡도에서 문제가 발생했을 것이라는 의견이 있었다. 내가 작성한 코드는 반복문을 사용했는데 제곱을 하는 것을 반복하는 것이기때문에 O(n^2)이 되어버린다. 그렇다면 반복문을 사용하는 것을 지양해야 한다. n^2이 아니라 logN이 되게끔 만들어본다면 어떨까? logN을 만드는 것은 반으로 무언가를 계속 쪼개는 것이다.
2^6을 예를 들어 생각해보자 2를 6번 곱해야하는 식인데 우리는 첫번째 코드에서의 발견처럼 2를 우선 C로 나누고 6번 곱하고 마지막으로 C로 나누면 된다.
2^6은 2^3 과 2^3의 곱과 같다. 그리고 2^3d은 2^1 과 2^2의 곱으로 나타낼 수도 있다. 또 2^2는 2^1 과 2^1의 곱으로 나타낼 수 있다. 이것을 재귀함수와 연관지어서 생각하면 된다. 우리는 B에 관해서만 잘 생각해보면 되기 때문에 B를 중심으로 코드를 작성해보자.
B가 0일 때는 무조건 1을 return 한다. 그리고 1일때에는 A%C를 return하고, B가 짝수일 때는 반으로 쪼갠 함수, 홀수일 때에는 하나는 반으로 쪼갠 값과 반으로 쪼갠 값에 +1을 한 함수를 호출하면 된다.
코드를 살펴보자.
#include <iostream>
using namespace std;
long long A, B, C;
long long Power(long long B) {
if(B == 0) return 1;
if(B == 1) return A%C;
if(B%2 == 0)
{
return ((Power(B/2) % C) * (Power(B/2) % C)) % C;
}
else{
return ((Power(B/2) % C) * (Power(B/2 + 1) % C)) % C;
}
}
int main(void) {
cin >> A >> B >> C;
cout << Power(B);
return 0;
}
