1629

날짜 : 2023. 04. 04

사용 언어 : python

 

문제

 

 

코드

import sys

def dac(a, b, c):
    if b == 1:
        return a % c
    if b % 2 == 0:  # 횟수가 짝수
        return (dac(a, b // 2, c) ** 2) % c
    else:
        return ((dac(a, b // 2, c) ** 2) * a) % c


a, b, c = map(int, sys.stdin.readline().split())  # a를 b번 곱한 후 c로 나머지 구하기
print(dac(a, b, c))

 

 

풀이

- 단순 for문으로 사용한다면 int값의 초과, 시간초과가 발생하기 때문에 분할정복을 이용하여 문제를 풀이한다.

- 두 수의 지수의 경우 다음과 같은 방식으로 변형이 가능하다.

기본 : a^b

b가 짝수 : a^b = (a^(b/2)) * (a^(b/2))

b가 홀수 : a^b = a * (a^(b/2)) * (a^(b/2))

- 상단 코드에 나타난 메소드를 활용해서 a^(b/2)를 c로 나눈 나머지로 표현한다면 dac(a, b//2, c) 로 표현이 가능하다.

 

알게된 점

- b값에 따라 짝수, 홀수로 나누어 분할정복을 이용해 풀이하는 방식이었다. 

- 분할정복 개념은 알고 있었지만 아직 연습이 부족한 것 같다.

 

 

참고 사이트

-