백준 1629 - 곱셈 (Python3)

코드

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

def solution(a, b, c):
    
    # b가 1이 될 때까지 분할 정복 수행
    # b가 1이면 a % c가 정답
    if b == 1:
        return a % c
    
    # 분할 정복(재귀) 실시
    tmp = solution(a, b//2, c)
    
    # a^b가 주어질 때 (a는 밑, b는 지수)
    # b가 짝수이면
    # a^b == a^b//2 * a^b//2
    if b % 2 == 0:
        return tmp * tmp % c
    # b가 홀수이면
    # a^b == a^b//2 * a&^b//2 * a
    else:
        return tmp * tmp * a % c
    
print(solution(a, b, c))    

문제 해설

분할 정복, 지수 법칙, 모듈러 연산의 분배 법칙을 활용하여 풀 수 있는 문제.

어렵지 않은 수준의 수학적 이해도를 요구하는 문제이지만, 이를 분할 정복으로 나타내는 방법 자체를 파악하지 못해 애를 많이 먹은 문제이다.

일단 기본적으로 아래의 두 성질을 이해하고 있어야만 문제를 풀 수 있다.

---

모듈러 연산의 분배 법칙

• 기본적으로 분배를 하면 분배된 모든 항에 모듈러 연산을 동일하게 적용해주고, 원래의 연산도 처리해준다.
• 단, 음의 항에 분배하는 경우 나눠주는 값 만큼 따로 값을 더해준 후에 최종 모듈러 연산을 수행한다.

지수 법칙 (곱하기 성질)

• 지수 법칙은 너무 간단하므로 별 설명을 하지 않겠다.

---

# 분할 정복(재귀) 실시
    tmp = solution(a, b//2, c)
    
    # a^b가 주어질 때 (a는 밑, b는 지수)
    # b가 짝수이면
    # a^b == a^b//2 * a^b//2
    if b % 2 == 0:
        return tmp * tmp % c
    # b가 홀수이면
    # a^b == a^b//2 * a&^b//2 * a
    else:
        return tmp * tmp * a % c

두 성질을 위의 코드와 같이 분할 정복을 통한 재귀적 호출로 표현하는 방법을 이해하는 것이 어려웠다.

결국 지수인 b를 2로 계속해서 나눠주면서 b가 짝수인지 홀수인지에 따라 반환되는 값을 선택하여 재귀를 종료해주면 최종적으로 원하는 결괏값에 도달할 수 있다는 것을 알게 되었다.

어찌보면 간단한 수학적 이해만을 가지고도 풀 수 있는 문제이지만, 역시 이것을 코드로 구현하는 것은 다른 차원의 문제이다. 많은 연습을 통해서 머리 속의 생각을 코드화시킬 수 있게 끝없이 반복해야겠다.