[백준 알고리즘] 백준 1629번 곱셈 파이썬(Python)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 1629번 곱셈 파이썬(Python)

1) 문제번호 : 1629번

 

2) 문제 출처

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

1629번: 곱셈

 

2. 문제

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

 

3. 제약사항

4. 입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

 

5. 출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

 

6. 풀이

- 반복문으로 풀었는데, 시간초과가 났다.

- 이 문제는 반복문으로 푸는게 아니라, 분할 정복(Divide And Conquer)으로 풀어야 한다.

- 분할정복은 간단하다.

- 예를 들어, 2^10은 2^5 * 2^5으로 나타낼 수 있다.(지수가 짝수일 경우)

- 그리고, 2^11은 2^5 * 2^5 * 2로 나타낼 수 있다.(지수가 홀수일 경우)

- 즉, 정해진 값을 절반으로 나눠서 계산하면 된다.

 

7. 소스 코드

import sys
input=sys.stdin.readline

# 값 입력
A, B, C = map(int, input().split())

# 분할 정복
def DaC(a,b) :
    if b==1 :
        return a % C

    temp = DaC(a, b // 2)
    
    # 짝수라면 temp * temp를 하면 된다.
    if b % 2 == 0 :
        return temp * temp % C
    
    # 홀수라면 temp * temp * a를 하면 된다.
    else :
        return temp * temp * a % C

print(DaC(A,B))

 

---