백준 1629 풀이 (곱셈, 분할정복, 파이썬)

이번 문제 상당히 어려웠다. 심지어 풀이로직보고 코드를 짜보았는데 96%까지 올라가고 계속 틀리길래 진짜 머가 문제인지 한참 헤맸다.

문제를 보면 어찌보면 상당히 간단하다. a**b % c를 하면 시간이 상당히 오래걸리니까 이걸 분할정복으로 풀어보라는 소리다.

솔직히 이거 재귀쓰면 더 오래걸릴거 같아서 손을 계속 못댔다. 그래서 고수의 풀이를 살짝 봤더니 b를 분할해서 구하는 것을 알 수 있었다......ㄷㄷ 천재인가

진짜 상상도 못했다. 분할이니까 무언가를 분할해야한다고 생각했다면 접근했을수도 있었지만 재귀면 무조건 오래걸린다는 생각에 갇혔던 것이었다.......

 

여튼 원리는 아래와 같다.

10**10 = 10**5 x 10**5 로 만들 수 있다.

10**5 = 10**2 x 10**2 x 10 으로 만들 수 있다.

10**2 = 10**1 x 10**1 로 만들 수 있다.

그렇다면 이걸 재귀로 푼다고 생각하면 3번의 재귀만으로 10**10연산을 구할 수 있는 것이다. 엄청나다!

따라서 b를 반으로 쪼개서 재귀를 계속 진행시키면 구할수 있다.

 

여기서 포인트는 

1. 쪼갠 b가 홀수인지 짝수인지

2. 언제 c로 나눈 나머지를 구할건지

3. a자체가 c보다 클때 어떻게 할건지

이러한 포인트를 명심하고 코드를 짜면 아래와 같다.

 

a,b,c = map(int, input().split())

def div(a, b, c):
    if b == 1:
        return a % c
    tmp = div(a,b//2,c)

    if b % 2 == 1:
        return tmp**2 * a % c
    else:
        return tmp**2 % c
print(div(a,b,c))

결론은 재귀가 항상 느리기만 하다는 고정관념을 버리자! 로직만 훌륭하면 재귀는 엄청나질 수 있다.