백준 1629. 곱셈 - 실버 1

1629번: 곱셈 (acmicpc.net)

1629번: 곱셈

 

---

분할정복을 이용한 거듭제곱 구하기인 줄 알았다. 
나름 도전해보면서 DP 문제처럼 mem이라는 리스트도 사용해보았으나 실패한 흔적이다.

import sys

sys.stdin = open("sample.txt", "r")
A,B,C = map(int, sys.stdin.readline().split())

mem = dict()
mem[1] = A

def n_square(n, k):
    if k not in list(mem.keys()):
        mem[k // 2] = n_square(n, k // 2)
        if k%2 == 0:
            mem[k] = mem[k // 2] * mem[k // 2]
        else:
            mem[k] = mem[k // 2] * mem[k // 2] * mem[1]
        return mem[k]
    else:
        return mem[k]

print(n_square(A, B)%C)

 

 

문제 풀이에 실패하고 구글링한 결과, 모듈로 연산은 다음과 같이 분배법칙이 성립한다.
이 문제에서는 마지막 줄의 곱셉에 주목해보면 구하고자 하는 값은 좌변에 있고 우리가 계산해야할 방식은 우변에 있다.

모듈로 연산의 분배법칙

import sys

sys.stdin = open("sample.txt", "r")
A,B,C = map(int, sys.stdin.readline().split())

mem = dict()
mem[1] = A % C

def n_square(n, k):
    if k not in list(mem.keys()):
        mem[k // 2] = n_square(n, k // 2)
        if k%2 == 0:
            mem[k] = mem[k // 2] * mem[k // 2]
        else:
            mem[k] = mem[k // 2] * mem[k // 2] * mem[1]
        return mem[k] % C
    else:
        return mem[k] % C

print(n_square(A, B)%C)