자연수 A를 B번 곱한 수를 알고 싶다.
단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.
a, b, c = map(int, input().split())
def solution(a, b, c):
if b == 1:
return a % c
temp = solution(a, b // 2, c)
if b % 2 == 0:
return temp * temp % c
else:
return temp * temp * a % c
print(solution(a, b, c))
단순한 문제이지만 단순하게 풀면 시간 초과가 된다!
이런 경우에 분할 정복 이라는 개념이 필요하다.
크고 방대한 문제를 조금씩 조금씩 나눠 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념이다. 대표적으로는 퀵소트나 병합정렬이 있다.
위 문제에서는 b의 경우에 따라 케이스를 나눠 전체 연산의 수를 줄여준다. 이 방법으로 시간 초과를 피할 수 있다.