달팽이는 올라가고 싶다 성공다국어

한국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.15 초 (추가 시간 없음) (하단 참고)

128 MB

177195

50254

42498

29.374%

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

2 1 5

5 1 6

100 99 1000000000

999999901

solve>

간단해 보이지만 생각보다 복잡한 문제다.

V/(A-B)로 계산하면 안된다.

예를 들어 설명해보겠다.

V가 100, A가 99, B가 98이라 가정했을 때

V/(A-B)로 계산하면 총 100일이 걸리는 것처럼 계산된다.

그러나 한 눈에 봐도 알 수 있다시피 2일이 걸린다.

99-98+99 하면 100을 바로 뛰어넘기 때문이다.

이를 보정하는 방법에 대해서 설명하겠다.

우선 (V-A)/(A-B)를 해준다.

A-B만큼의 이동이 반복되는 동안에는 달팽이가 V를 뛰어넘지 못하도록 V를 V-A로 바꿔준다.

만약 (V-A)/(A-B)가 딱 떨어지는 나눗셈이라면 V가 되기 위해 달팽이가 A만큼 움직이는 횟수 1을 추가해준다.

나눗셈이 딱 떨어질 시 (V-A)/(A-B)+1이다.

아니라면 달팽이가 A-B만큼 한 번 더 움직이고 A만큼 다시 움직여주어야 하므로 2를 더해준다.

푸느라 머리 좀 쥐어뜯었다.;

그래도 이전에 푼 재귀문제들보단 (많이)나은 것 같다.