Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- spring oauth
- Kotlin
- Spring
- springboot
- 백준 17779
- 웹어플리케이션 서버
- re.split
- 백준 19238
- 백준
- sql 기술면접
- 백준 파이썬
- with recursive
- 백준 16719
- 백준 15685
- MSA
- Spring Boot
- Coroutine
- spring security
- 백준 17626
- 백준 16235
- java 기술면접
- JPA
- java
- MySQL
- 프로래머스
- spring cloud
- JVM
- 파이썬
- 백준 16236
- 프로그래머스
Archives
- Today
- Total
시작이 반
[백준] 1629번 (python 파이썬) 본문
SMALL
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모두 엄청 큰 숫자가 들어오면 변수에 담을 수 없다고 생각했다.
그래서 매번 연산마다 %c 연산을 해준다.
분배법칙을 보면 결국 같은 것을 알 수 있다.
a, b, c = map(int, input().split(' '))
def dnc(length):
if length == 1:
return a % c
if length % 2 == 0:
left = dnc(length // 2)
return left * left % c
else:
left = dnc(length // 2)
return left * left * a % c
print(dnc(b))
LIST
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 10816번번 (python 파이썬) (0) | 2021.03.16 |
---|---|
[백준] 1920번 (python 파이썬) (0) | 2021.03.16 |
[백준] 2168번 (python 파이썬) (0) | 2021.03.15 |
[백준] 20003번 (python 파이썬) (0) | 2021.03.14 |
[백준] 1780번 (python 파이썬) (2) | 2021.03.08 |