백준 1629번 곱셈 _ 분할정복 (python)

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

1629번: 곱셈

백준 1629번 분할정복

 

이번 1629번 문제를 통해서 알아볼 개념은 분할정복입니다.
이는 딱 명확한 알고리즘이 존재하는 것이 아닌, 구하려는 값이나 그 과정이 너무 계산하기 복잡할 때 이를 간단한 문제들로 쪼개서 푼 뒤, 이를 합친다라고 생각하면 되는데요. 

당장에 웹개발을 한참 공부하고 있는 저는 main.js 파일에 너무 많은 코드를 쓰다보면 나중에 오류가 발생했을 때 수정하기 어려울 뿐더러 스스로도 알아보기 힘들어 main.js에는 여러 js파일들을 import만 하고 다른 여러 파일들을 header footer block별로 구분하여 작성하는데요. 이 역시도 분할정복이라고 볼 수 있습니다.

그럼 이번 문제는 왜 분할 정복 문제인가?

쉽게 생각해보면 2147483647을 2147483647번 곱하는 명령만 돌려도 하루 종일 걸리실지도 몰라요..
저렇게 큰 수를 큰 수만큼 곱하는 연산을 간단한 문제로 쪼개서 합쳐야겠죠?

저는 이 문제를 이진법으로 접근했습니다.

사실 2147483647을 10번 곱하는 건 일도 아니에요, 하지만 10을 2147483647번 곱하는 건 매우 큰 일이랍니다.
이 문제는, 어떻게 B번 곱하는 복잡한 일을 최소화 할 수 있을까에 초점을 맞추어야했어요.
그래서 저는 B를 이진수로 표현한 뒤 연산하였는데요, 예를 들어볼게요.

10 11 12 의 숫자가 주어졌다면,

원래는 10을 11번 곱해야겠지만,
11을 [1,0,1,1]로 표현한다면,
10을 1번 곱한 뒤 12를 나눈 나머지,
10을 2번 곱한 뒤 12를 나눈 나머지, (10을 1번 곱한 뒤 12를 나눈 나머지의 제곱)
10을 4번 곱한 뒤 12를 나눈 나머지는 건너뛰고, (10을 2번 곱한 뒤 12를 나눈 나머지의 제곱)
10을 8번 곱한 뒤 12를 나눈 나머지, (10을 4번 곱한 뒤 12를 나눈 나머지의 제곱)
를 구한 뒤 그것들을 곱해주면 된답니다.

연산이 총 n번에서 log2(n)번으로 줄어들게 되는거죠!

만약 2147483647번 곱하는 일이 있다면,
이는 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 로 치환되어 약 30번의 연산만으로 해결 가능한 문제가 된답니다.

생각보다 구현은 간단했지만, 접근을 잘못하면 결코 시간 제한을 만족시키기 힘들었던 1629번 곱셈문제였습니다.

다음은 풀이 코드입니다.

[A, B, C] = list(map(int, input().split()))
b = []
current = -1
answer = 1

# B를 이진수로 b 리스트에 담기
x = 1
while(B>=x):x *= 2 
while(x!=1): 
    x /= 2
    if (B>=x):
        b.append(1)
        B -= x
    else: b.append(0)

# b 리스트 끝부터 시작하며 A를 B번 곱한 수를 C로 나눈 나머지를 answer에 저장
while(b != []):
    K = b.pop()
    if (current == -1): current = A%C
    else: current = (current*current)%C

    if (K==1):
        answer *= current
        answer %= C

print(answer)

 

끝!