목록백준 1629 (1)

시작이 반

[백준] 1629번 (python 파이썬)

A를 B번 곱한 수의 C로 나눈 나머지를 구하는 것이다. A, B, C는 모두 2,147,483,647 이하의 자연수다. 즉 반복문으로는 절대 풀수없다. 때문에 분할 정복을 선택하였다. 첫 풀이 a, b, c = map(int, input().split(' ')) def dnc(length): if length == 1: return a if length % 2 == 0: left = dnc(length // 2) return left * left else: left = dnc(length // 2) return left * left * a print(dnc(b)) 이렇게 푸니까 시간초과가 나왔다.. 검색해보니 오버플로우도 시간초과가 나온다고 한다.???음? 생각해보니 a, b모두 엄청 큰 숫자가 들어오..
알고리즘/백준 2021. 3. 15. 22:31
이전 Prev 1 Next 다음