풀이_1629.md

🕊 백준 1629 - 곱셈

• Date : 2021.06.06(일)
• Time : 10분

문제

• 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
  
  

코드 풀이

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

: 먼저 몇 번 곱해지는지에 따라 1번만 곱해진다면 곱셈의 이유가 없기 때문에 바로 a%c를 진행해준다. 그리고 2이상이 곱해진다면 일단 pow 함수를 이용해 b//2 번만 곱해준다. 그리고 b가 홀수인지 짝수인지를 구분해서 다시 곱해준다.