[Python/파이썬] 백준 알고리즘 2869번 - 달팽이는 올라가고 싶다

개인적으로 풀면서 재밌었다.

그래서 포스팅하려고 한다.

 

 

 

<풀이>

A, B, V = map(int, input().split())

pre_move = (V-A) // (A-B)
remainder = (V-A) % (A-B)

if remainder > 0:
    print(pre_move + 2)
else:
    print(pre_move + 1)

V길이의 막대의 정상에 도달하는 시점은 분명 낮일 것이다.

근데 여기서 중요시 생각해야 될 것은 막대의 정상에 도달하는 시점은 달팽이가 낮에 움직일 수 있는 최대의 거리만큼을 이동함과 동시에 도달하는 것이 아닐 수 있다는 것이다.

다시 말해서, 정상에 도달하고도 달팽이는 더 움직일 수 있지만 정상에 도달했기 때문에 멈추는 경우가 있을 수 있다는 것이다.

때문에 우선 나는 막대의 길이 V에서 달팽이가 낮에 최대로 움직일 수 있는 거리인 A를 뺐다.

이 상태에서 하루(낮+밤)에 이동하는 거리인 A-B로 나눈 몫을 구하면(//) 달팽이가 정상에 도달하기 근처의 날까지를 구할 수 있다.

이것이 pre_move 변수에 들어가는 값이다.

 

그리고 여기서 중요한데 방금 몫을 구하는 계산에서 몫말고 나머지도 구한다.(%) 이 값은 remainder 변수에 들어간다.

 

달팽이가 하루에 갈 수 있는 최대 거리는 A이다. 만약 remainder가 0보다 크다면 달팽이는 pre_move + 1 의 기간으로는 정상에 도달할 수 없다는 이야기이다. (0초과 A미만의 거리가 남을테니)

따라서 하루를 더 이동해야한다. 그러므로 pre_move에 +2를 해줘야한다.

만약 remainder가 0으로 나누어 떨어졌다면 다음날 낮에 최대 거리만큼 이동하면 최대 거리만큼 딱 이동함과 동시에 정상에 도달할 수 있다. 따라서 pre_move에 +1만 해주면 된다.

 

 

 

<핵심 정리>

1. 개발자에게 중요한 것은 코딩 능력보다도 문제 해결 능력인 것 같다.

 

 

+23.09.25 추가)

복습하다가 새로운 풀이가 생각났다.

import math

A, B, V = map(int, input().split())

print(math.ceil((V-A)/(A-B)+1))

풀이를 설명하면 다음과 같다.

달팽이는 낮에 A만큼 올라가고 밤에 B만큼 미끄러진다.

즉 하루 동안 A-B만큼 올라간다.

이 때 간과하면 안되는 부분이 있는데, 달팽이가 정상에 도달하는 때는 낮이라는 것이다.

따라서 달팽이가 정상에 도달하기까지의 날까지의 일수를 x라고 하면,

(A-B)(x-1) + A >= V 가 성립되는 x를 구하면 되는 것이다.

위 부등식을 x에 대해 정리하면 x >= (V-A) / (A-B) + 1 이 된다.

그러므로 (V-A) / (A-B) + 1 의 소숫점을 올림해주면 x값이 나온다.

 

이를 정리하면 위 작성한 코드와 같다. (파이썬에서 올림은 math모듈의 ceil()을 사용한다)