728x90
문제
1629번: 곱셈
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
www.acmicpc.net
문제가 단 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로 나눈 나머지를 반환하는 로직
- 분할 정복 알고리즘은 일반적으로 다음과 같은 세 단계로 진행
- 분할(Divide): 원래 문제를 작은 부분 문제로 나눔 보통 문제를 동등한 크기의 부분 문제로 나눔
- 정복(Conquer): 작은 부분 문제들을 재귀적으로 해결, 작은 부분 문제의 크기가 충분히 작으면 직접적으로 해결
- 조합(Combine): 작은 부분 문제들의 해를 조합하여 전체 문제의 해결
'프로그래밍 > 알고리즘' 카테고리의 다른 글
DP 점화식 손으로 정리하기(파이썬) (0) | 2023.04.12 |
---|---|
프로그래머스 - 숫자 문자열과 영단어 파이썬 (0) | 2023.04.11 |
알고리즘 최강자 찾기 (0) | 2023.04.05 |
백준 14501 - 퇴사 파이썬 (0) | 2023.03.28 |
백준 9465 - 스티커 파이썬 (0) | 2023.03.27 |
댓글