[ BOJ / 파이썬 ] 1629. 곱셈

간단한 재귀 문제인데, 수학적 개념이 약해 감을 잡기 어려웠다.

나머지에 대한 원리를 이해한 뒤 재귀적으로 코드를 풀어내는 것 자체는 비교적 수월하게 작성했다.

 

예시의 10, 11, 12 input에 대하여

10^11 % 12 = ??

10^1 * (10^5 % 12)^2 = 

10^1 * (10^1 * (10^2 % 12)^2) =

10^1 * (10^1 * (10 % 12)^2)^2) =..

 

요렇게 쪼개 나갔다. 

 

제출 1. 실패 -> 시간초과.

getMod를 두 번 부르게 되며 매 연산마다 반으로 나눠 logN으로 나누는 이득을 전혀 못 보게 했다. 그래서 시간초과 남..

def getMod(a, b, c):
  if b == 1:
    return a % c
  return a**(b%2) * getMod(a, b//2, c) *getMod(a, b//2, c) %c

def main():
  a, b, c = map(int, input().split())
  print(getMod(a, b, c))
  
if __name__ == '__main__':
  main()

 

해당 부분 수정하였다.

한 번 재귀로 들어가는 부분을 temp에 저장해 그 값을 두 번 곱하게 함.

 

제출 2. 통과

def getMod(a, b, c):
  if b == 1:
    return a % c
  temp = getMod(a, b//2, c)
  return a**(b%2) * temp * temp % c

def main():
  a, b, c = map(int, input().split())
  print(getMod(a, b, c))
  
if __name__ == '__main__':
  main()

 

한 5개월 전에 해당 문제를 푼 기록이 있는데 그 때 풀이보다 시간소요가 절반으로 줄어 기분이 좋아졌다. 흐헤

 

과거 풀이. 통과. 

import sys
input = sys.stdin.readline

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

def rec(a, b, c):
  if b == 1:
    return a % c
  temp = rec(a, b//2, c)
  if b % 2 == 0:
    return temp * temp % c
  if b % 2 == 1:
    return temp * temp * a % c
print(rec(a, b, c))

b % 2 의 차이를 안 두고 그냥 곱해도 되는데 그걸 구분하는 연산이 한 번 더 들어가서 그런 듯하다.

a ^ (b%2) 로 할 때 어차피 b%2 == 0이라면 해당값이 어차피 1되기때문에 곱셈값에는 영향을 안 미치게 되므로 구분지어주기 위한 연산을 한 번 더 할 필요가 없었던 것!

 

아 점점 머리가 좀 구조적으로 사고하는 것 같아 너무 만족스럽다. 헤헤