문제
땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.
달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.
달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)
출력
첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.
내 풀이
a, b, v = map(int, input().split())
height = 0
i = 1
while True:
height += a
if height >= v:
break
else:
height -= b
i += 1
print(i)처음에는 너무나도 정직하게 반복문으로 a를 더하고 높이에 도달했는지 확인하면서 b를 빼고 걸리는 날짜를 계산했다...그러나 문제 조건에서 알 수 있듯 최대 까지 수가 커지기 때문에 이런 반복문은 naver...
아래는 반복문을 쓰지 않고 접근하여 정답을 받은 코드이다.
a, b, v = map(int, input().split())
i = (v-a)//(a-b)
rest = (v-a)%(a-b)
if rest == 0:
print(i+1)
else:
print(i+2)코멘트
문제의 조건에서 보이듯 반복문으로 접근하면 시간 초과가 뜨면서 오답 처리가 된다. 예제 3만 돌려봐도 결과를 받는데 한참 걸림을 알 수 있다...그러니 이는 반복문으로 접근하면 안되는 문제이다.
그래서 생각해낸 방법은, v = a*(i+1) - b*i를 만족하는 i를 찾는 것이다. 이 문제에서 함정은 낮에 꼭대기에 도달하면 밤에 잠을 자면서 미끄러져서 하루를 더 사용할 필요가 없다는 것이다. 예제 입력1의 예시로 보면, 낮에 2m를 가고 밤에 1m를 미끄러지기 때문에 결국에는 하루에 1m씩 가서 총 5일 걸릴 것 같지만, 사실은 3일차까지 3m를 진행한 이후에 4일차 낮에 2m를 올라가면 꼭대기에 도달하기 때문에 밤에 자면서 미끄러질 일이 없는 것이다. 이를 반복문을 사용하지 않고 어떻게 고려할 것인가가 관건이었는데, a에 i이 아닌 i+1를 곱함으로써 이를 해결할 수 있었다. 이를 만족하는 i는 위 코드에서 볼 수 있듯이 (v-a)//(a-b)를 계산해서 구할 수 있고, 이 연산이 나머지 없이 딱 나누어 떨어진다면 i+1일 차에 꼭대기에 도달하지만, 나머지가 있다면 하루가 더 걸리므로 i+2일차에 꼭대기에 도착하게 하면 정답이다.
References
