2869번(달팽이는 올라가고 싶다) 파이썬(Python) 풀이 공유

들어가며

문제의 내용을 보기 전에 꽤 낮은 정답률(28.049%)을 보고 흥미가 더 생겼던 문제이다. 그런데, 생각보다 매우 간단한 문제라서 허무하게 끝난 것 같다. 아래 그림은 어려울 것 같은 문제는 비교적 쉽게 풀리고, 쉬울 것만 같은 문제는 생각하지 못한 곳에서 오류가 발생하는 상황을 너무나도 잘 나타내주어 정말 공감된다.

문제

• 2869번 달팽이는 올라가고 싶다

시간 제한	메모리 제한
0.15 초(추가 시간 없음)	128 MB

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

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

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

입력

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

출력

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

예제

입력	출력
2 1 5	4
5 1 6	2
100 99 1000000000	999999901

풀이

문제를 이해하는데에는 그리 어렵지 않았지만, 약간 애매하다고 느낀 부분이 있었는데, 이 부분은 아래와 같이 가설을 세우고 문제에 접근하였다.

달팽이가 처음 막대에 올라간 시점은 낮으로 한다. 따라서, 소요 일수에 1을 더하고, 막대 높이에서 처음 막대에 올라간 낮에 이동한 거리만큼 거리를 빼준다.

달팽이는 하루에 이동할 수 있는 거리가 제한되어 있는데, 이 기준이 시간이 아니라 하루 단위이기 때문에 지문을 보자마자 단서를 찾으려고 몇 번이고 읽어보았다. 하지만, 별 다른 단서가 없어서 달팽이가 움직이기 시작하는 시점, 즉, 처음 막대에 발을 디딘 그 시점은 분명히 낮일거라고 생각하여 위와 같은 가설을 세웠다.

코드로 구현할 때 처음에는 while 문으로 구현하려고 했으나, 입력 값의 범위(1,000,000,000)를 고려하여 공식을 세워야겠다고 생각했다. 위에서 잠깐 언급했지만, 달팽이의 하루동안 이동 가능한 거리는 분명히 제한되어 있다. 낮과 밤을 포함하여 하루에 달팽이가 이동한 거리(M)를 식으로 표현하면 아래와 같다.

M = A - B

즉, 낮에 이동한 거리에서 밤에 미끄러진 거리를 뺀 값이 하루 총 이동 거리가 된다. 그러면 소요일수를 구하는 것이 매우 간단해지는데, 이는 막대 높이를 하루 이동 거리로 나누면 되기 때문이다. 단, 앞에서 언급한 가설을 적용해야 하는데, 총 소요 일수(D)를 식으로 표현하면 아래와 같다.

D = ((V - A) / (A - B)) + 1

위에서 언급한 가설 중에서 달팽이가 막대에 처음 발을 내딛은 순간을 포함시키기 위해 마지막에 하루를 추가하였다. 사실, 반나절이 맞을 텐데, 이 또한 하루에 포함되기 때문에 1일로 적용하였다. 그리고 막대 높이에서 낮 동안 이동한 거리를 빼주는 방식으로 구현하였다. 연산 결과는 소수점이 포함되는 float 형태로 출력되는데, 소수점이 있다는 의미는 곧 하루가 더 소요된다는 의미이므로 무조건 ceil 함수로 올림처리하여 계산하였다. 위의 모든 내용을 토대로 작성한 코드는 아래와 같다.

from math import ceil

A, B, V = map(int, input().split(" "))
print(ceil((V - A) / (A - B)) + 1)

• Line 1 : 소숫점을 올림하기 위해 math 모듈에서 ceil 함수를 불러온다.
• Line 3 : 입력 값으로 낮 동안 이동거리, 밤 동안 미끄러진 거리, 막대 높이를 받아오는데, 공백을 기준으로 나누어 수치형으로 변환 후 각각 변수 A, B, C에 초기화한다.
• Line 4 : 위의 공식을 적용하여 계산한 값을 출력한다.

마치며

다른 사람들은 어떻게 제출했는지 궁금해서 먼저 숏코딩에 들어가보았는데, 아래 코드를 살펴보고는 신선한 충격을 또 한 번 받았다.

a,b,v=map(int,input().split())
print(1-(v-a)//(b-a))

위의 코드를 풀어보자면, 내가 했던 방식인 뒤에서 하루를 더해주는 게 아니라 나눠주는 값(b-a)을 음수로 만든 다음에 빼주는 방식을 적용한 것을 확인할 수 있다. 그러면, 연산 과정에서 값은 양수로 바뀌고, 이때 하루가 더 추가된 후 올림 처리까지 된다. 알고리즘에 막 입문한 내가 느끼기에는 마치 큰 벽을 만난 듯한 느낌이 드는 코드였다.