728x90
#1629번 곱셈 https://www.acmicpc.net/problem/1629
1629번: 곱셈
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
www.acmicpc.net
거듭제곱을 해결하는 문제인데, 자료구조 수업에서 다룬 적이 있던 것 같다.
틀린 코드
from sys import stdin
input = stdin.readline
a, b, c = map(int, input().split())
def fpow(C, n):
if n == 1:
return C
else:
x = fpow(C, n//2)
if n % 2 == 0:
return x * x
else:
return x*x*C
print(fpow(a, b) % c)
단순히 분할정복을 있는 그대로 구현했다. 하지만 시간초과가 나서 당황했다.
정답 코드
from sys import stdin
input = stdin.readline
a, b, c = map(int, input().split())
def fpow(C, n, z):
if n == 1:
return C % z
else:
x = fpow(C, n//2, z)
if n % 2 == 0:
return x * x % z
else:
return x*x*C % z
print(fpow(a, b, c))
문제에서는 정답을 c라는 수로 나눈 나머지만 구하는건데 이를 모든 연산에 적용했을 때 시간초과가 발생하지 않는다.
마지막에 도출된 큰 수에 나머지 함수를 적용하면 시간초과가 난다.
이유는..?
많은 자료를 찾아봤지만 만족스러운(충분히 납득할만한) 답을 얻지 못했다.
아무튼 수가 커질수록 굉장히 오래걸린다는 점은 확실하다.
'Algorithm > acmicpc.net' 카테고리의 다른 글
파이썬 시간초과는 논리도 필요해요. (#14888 연산자 끼워넣기) (0) | 2024.03.20 |
---|---|
오랜만에 돌아온 알고리즘! 브루트포스 (#1062번 가르침) (0) | 2024.01.08 |
처음보는 유형 (#5525번 IOIOI) (0) | 2022.03.19 |
DP는 아직 어렵.. (#17626 Four Squares) (0) | 2022.03.18 |
가벼운 DP - 시간 복잡도를 고려한 (#9461번 파도반 수열) (0) | 2022.03.18 |