-
[열 번째](문제 번호 : 2869, 달팽이는 올라가고 싶다) 도전백준 문제 풀이 2023. 8. 3. 22:03
1. 문제 요약
땅 위에 달팽이가 있다. 낮에는 나무를 A만큼 올라가고, 밤에는 B만큼 미끄러진다.
이때, V까지 도달하는데 걸린 D를 출력하면 된다.
예시.
입력
5 1 6
출력
2
2. 풀어보기
이 문제는 겉보기에는 쉬워보였다. 하지만 V의 최대 크기는 1000000000(10억)이다.
평범하게 while이나 for 반복문으로 하면 10억번의 반복문을 타야되어서, 시간초과가 발생한다.
예를 들어, 아래와 같은 코드..
A, B, V = map(int, input().split()) D = 0 while V > 0: D += 1 V -= A if V <= 0: break V += B print(D)
즉, 예상되는 반복 횟수를 먼저 계산해 A-B만큼을 어느 정도 증가 시킨 뒤에, 반복문을 실행시키면 좋을 것 같았다.
일반적인 재귀 함수의 최대 재귀 횟수는 약 천 번이므로, 이 천 번을 기준으로 하려한다.
또한, 마지막 날에는 A만이 증가하면서 V에 달성하는 것을 고려한다.
1. V/(A-B) >= 1000 일 경우, V//(A-B) - A = R이라 하고, V - (A-B)*R, D += R 하여 V의 크기를 대폭 줄인다.
2. 위의 일반적인 반복문을 실행한다.
3. 풀이 코드
1. V/(A-B) >= 1000 일 경우, V//(A-B) - A = R이라 하고, V - (A-B)*R, D += R 하여 V의 크기를 대폭 줄인다.
A, B, V = map(int, input().split()) D = 0 if V/(A-B) >= 1000: R = V//(A-B) - A V -= R*(A-B) D += R
2. 일반적인 반복문을 실행한다.
while V > 0: D += 1 V -= A if V <= 0: break V += B print(D)
'백준 문제 풀이' 카테고리의 다른 글
[8일차](문제 번호 : 11005, 진법 변환 2) 도전 -2 (0) 2023.07.27 [7일차](문제 번호 : 11005, 진법 변환 2) 도전 -1 (0) 2023.07.24 [6일차](문제 번호 : 2745, 진법 변환) 도전 (0) 2023.07.23 [5일차](문제 번호 : 2536, 색종이) 도전 (0) 2023.07.22 [4일차](문제 번호 : 2566, 최댓값) 도전 (0) 2023.07.21