(알고리즘) 백준1629 python 파이썬

문제

문제를 살펴보자
백준 1629 곱셈 : https://www.acmicpc.net/problem/1629

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

예제입력

10 11 12

예제출력

4

풀이방법

해당 문제를 살펴보면 그냥 어? 곱하고 나누고 곱하고 나누고 하면 되는거 아닌가? 라는 생각이 들 수 있다. 하지만 입력으로 주어진 B를 살펴보자.
B의 최대값은 2,147,483,647이다. 시간복잡도를 N으로 풀어도 이미 시간초과가 나버린다. 그렇다면 어떻게 풀어야 할까? 방법은 분할정복이다.
((a^n)%c * (a^n)%c)%c는 (a^(n*2))%c이다.(나머지 정리)
이를 활용하여 리턴값이 있는 함수를 만들고 n의 값이 반으로 나누어 떨어지면
((a^n)%c * (a^n)%c)%c를 리턴하고
아닐 경우는 ((a^n)%c * (a^n)%c * a%c)%c를 리턴한다.
이때 n이 1이 될 경우에는 a%c를 리턴한다.
이 함수를 재귀적으로 구현하면 해결된다.

코드

a,b,c=map(int,input().split(' '))
a%=c #미리 나머지를 구해둔다

def solution(n):
    if(n==1):
        return a

    r=solution(n//2)#(a^(n//2))%c를 구한다 
    
    if(n%2==0):#2로 나누어 떨어지면
        return (r*r)%c #((a^(n//2))%c * (a^(n//2))%c)%c는 (a^(n))%c를 활용해서 리턴하고
    else:#홀수이면
        return (r*r*a)%c # 추가로 a를 곱한 후 나머지를 구해서 리턴한다

print(solution(b))

후기

간단한 분할정복 문제였다. 처음에 문제를 보고 그냥 for문을 돌렸으나 살펴보니 B의 값이 20억이 넘어가고 있었다. 입력값을 잘 살펴 어떤 알고리즘을 쓸지 항상 고려하는 습관을 길러야 하는데 이게 아직 무턱대고 문제부터 푼다. 노력해야겠다.