백준 1629번

leejm·2022년 11월 19일
0

문제

자연수 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의 경우에 따라 케이스를 나눠 전체 연산의 수를 줄여준다. 이 방법으로 시간 초과를 피할 수 있다.

profile
Python Based Backend Engineer입니다. DevOps와 효율적으로 일하는 것에 관심이 있습니다.

0개의 댓글