[Python] 백준 풀기 1629 - 곱셈

파이썬 백준 1629번

실버1

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

1629번: 곱셈

 

 

 

문제 보기

분류: 수학, 분할 정복을 이용한 거듭제곱

 

 

 

문제 풀기

일단 수학적 이해가 우선시되는 문제였다. 백준의 분할 정복 묶음에서 맵 형식만 다루다 보니까 어떤 식으로 접근을 해야 하는지 감이 오지 않았다. 그래서 다른 풀이를 참조를 하였고 거듭제곱 꼴이니 이를 곱셈 분할로 다가가면 된다는 것을 쉽게 이해할 수 있었다. 하지만, 코드의 진행을 따라가도 이해되지 않는 부분이 있었는데 그것은 나머지에 대한 부분이었다. 나머지 분배 법칙에 대한 수학적 이해가 필요한 부분이었는데 이것을 알지 못하면 해결하지 못할 문제인 것 같다. 나머지 분배 법칙의 공식을 바라보니 내가 정규 교육 과정 시간에 졸았나? 하는 느낌이 들었다. 흠..

따라서 문제 해결 방법은 거듭제곱의 형태를 분할하여 계산하고 문제에서 제시한 나머지의 결과를 표시해야 하기 때문에 나머지 분배 법칙을 적용해야 한다.

 

(A * B) % C    =    ((A % C) * (B % C)) % C

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline

def fnRemainderDistribution(A, B):
    if B == 1:
        return A % C
    
    remainder = fnRemainderDistribution(A, B // 2)
    print(f'remainder: {remainder}')            # test print
    
    if B % 2 == 0:
        return remainder * remainder % C
    elif B % 2 == 1:
        return remainder * remainder * A % C


if __name__ == "__main__":
    A, B, C = map(int, inputdata().split())
    
    result = fnRemainderDistribution(A, B)
    print(result)



# 111 123 17

# remainder: 9
# remainder: 15
# remainder: 2
# remainder: 2
# remainder: 4
# remainder: 8
# 15

 

 

 

추가 하기

나머지 연산 분배 법칙에 대해 알아보자

https://velog.io/@gidskql6671/%EB%82%98%EB%A8%B8%EC%A7%80Modulo-%EC%97%B0%EC%82%B0-%EB%B6%84%EB%B0%B0%EB%B2%95%EC%B9%99

나머지(Modulo) 연산 분배법칙

 

(A + B) % p   =   ((A % p) + (B % p)) % p
(A * B) % p   =   ((A % p) * (B % p)) % p
(A - B) % p   =   ((A % p) - (B % p) + p) % p
(A / B) % p   =   (A * B^(p-2)) % p = ((A % p) * (B^(p-2) % p)) % p