백준 1629 - 곱셈

https://www.acmicpc.net/problem/1629

1629번: 곱셈

한 줄 요약 : 맞는데 왜 틀렸지? 싶으면 곱셈 값을 long long에 저장하자

 

분할정복을 통한 거듭제곱과 나머지 정리를 사용하면 답은 구할 수 있다.

 

분할정복 : 제곱수 base^expon를 다음과 같이 구한다.

0) expon이 1일 경우 base

1) expon이 짝수 2k일 경우 (base^k)*(base^k)

2) expon이 홀수 2k+1일 경우 (base^k)*(base^k)*base

 

나머지 정리 : (a*b) % c = (a % c) * (b % c) % c

ex) (8*7)%5 = 56%5 = 6, (8*7)%6 = (3*2)%5 = 1

 

이 두 개념을 조합하고 오버플로우만 신경써주면 답이 나온다.

자주 틀리는 반례. 분할 정복이 진행되다보면 expon = 3에서

(99999 % 100000)*(99999 % 100000)*99999 라는 연산을 수행하게 되는데, 앞의 99999*99999만 먼저 계산해도 약 100억, INT_MAX보다 큰 값이 나오므로 값을 int에 저장하면 오버플로우가 발생한다.

 

다만 나는 구현을 이상하게 했는지 시간초과도 나오고 다른 풀이법이 있다고 해서 그 방법을 사용했다.

나머지 정리는 그대로 사용하되, 거듭제곱의 표현에 이진수를 사용하는 것이다.

 

예를 들어 (5^17)%7에서 제곱수 17은 이진수로 10001, 즉 16 + 1이다.

따라서 배열에 (5^1) % 7, (5^2) % 7, (5^4) % 7, (5^8) % 7, (5^16) % 7을 저장해두고,

이 중 5^1과 5^16의 나머지만 곱해주고 나머지 정리를 사용하면 된다.

 

;;

문제를 풀면서 계속 시간초과나 틀렸습니다가 떠서 당황했는데, 일일히 문제점을 찾아보니 곱셈의 결과값을 int에 저장하려 해서 생긴 문제들이였다. A나 B가 INT_MAX에 가까운 값이면 계산 과정에서 int 변수들은 오버플로우가 발생할 가능성이 매우 높으므로, 웬만하면 long long을 사용하자.

 

배운 내용

 

분할정복 복습과 시간복잡도

 

위 문제를 분할정복으로 구현하면 input size n(여기서는 B가 n이 된다)의 문제 T(n)은 2개의 T(n/2)로 쪼개지고, 다시 합칠 때는 상수 시간이 걸린다. T(n) = 2T(n/2)이므로 시간복잡도는 O(n)이 소요된다.

T(n) = 2T(n/2) = 4T(n/4) = ... = 2^(log n) T(1) = n

 

음? 풀이를 작성해보니 애초에 시간복잡도가 O(n)이므로 B의 값이 커지면 분할정복으로는 풀 수가 없었다. 이진수를 활용해 풉시다.

 

정석적인 분할정복 알고리즘으로 값을 구하면 시간복잡도는 O(n)이 소요될 것이다.

 

하지만, 제곱수 base^expon을 2개의 base^k로 나눌 때, base^k는 값이 같으므로 절반 크기의 연산을 굳이 2번씩 수행할 필요는 없다. 한 번 수행해 값을 저장하고 그 값을 제곱하면 된다. 이렇게 하면 시간복잡도가 O(log n)으로 기가 막히게 감소한다.