백준 1629 - 곱셈 파이썬

문제 

1629번: 곱셈

문제가 단 2줄이다 

이해도 쉬워서 엄청 빨리 풀줄 알았는데... 어려워서 다른 사람 코드 참고했다...

직접 계산한다면 시간초과가 날 문제이다  

 

def dac(a, b, c):
    if b == 1:
        return a % c  # b가 1일 때 a를 c로 나눈 나머지 반환

    if b % 2 == 0:
        return (dac(a, b // 2, c) ** 2) % c  # b가 짝수일 때, dac(a, b // 2, c)를 제곱한 값에 c로 나눈 나머지 반환
    else:
        return ((dac(a, b // 2, c) ** 2) * a) % c  # b가 홀수일 때, dac(a, b // 2, c)를 제곱한 값에 a를 곱하고 c로 나눈 나머지 반환

a, b, c = map(int, input().split())  # 입력으로 a, b, c 값을 받음
print(dac(a, b, c))  # dac 함수에 a, b, c 값을 전달하여 결과 출력

- 이 코드는 분할 정복(Divide and Conquer) 알고리즘을 사용하여 a를 b번 제곱한 값을 c로 나눈 나머지를 구하는 코드

- dac() 함수에서는 b의 값에 따라 재귀적으로 a를 제곱하고 c로 나눈 나머지를 계산하고,

- b가 짝수인 경우에는 그 결과를 다시 제곱하고 c로 나눈 나머지를 반환하고,

- b가 홀수인 경우에는 그 결과에 a를 곱하고 c로 나눈 나머지를 반환하는 로직

정복하기 어려운 정복알고리즘...

- 분할 정복 알고리즘은 일반적으로 다음과 같은 세 단계로 진행

1. 분할(Divide): 원래 문제를 작은 부분 문제로 나눔 보통 문제를 동등한 크기의 부분 문제로 나눔
2. 정복(Conquer): 작은 부분 문제들을 재귀적으로 해결, 작은 부분 문제의 크기가 충분히 작으면 직접적으로 해결
3. 조합(Combine): 작은 부분 문제들의 해를 조합하여 전체 문제의 해결