[백준 2869번] 달팽이는 올라가고 싶다

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

---

문제 상황

달팽이가 지면에서 V m 인 나무막대를 낮에는 A m 만큼 이동하고,
밤에는 B m 만큼 뒤로 미끌어진다. 단, 정상에 도달하면 미끌어지지 않는다.
이때, 달팽이가 V m 나무막대 정상에 도달하려면 며칠이 걸리는지 구하는 문제이다.
 
즉, 낮에 A m를 이동하고 밤에는 정상에 도달하지 않는다면, B m 를 뒤로 미끄러지고
정상에 도달하면 미끄러지지 않는 달팽이는
정상에 도달하기 위해선 며칠이 걸릴까?

---

솔루션

달팽이는 하루에 (A - B)m 만큼 이동한다.
정상에 도달하면 밤에는 0m 미끄러지고, 도달하지 않는다면, B m 만큼 미끄러진다.
 

달팽이가 정상에 도달하는 과정관찰

달팽이가 정상에 도달하는 과정을 전개하면, 다음과 같다.
( A - B ) + ( A - B ) + ( A - B)  - - -  ( A - B ) + ( A + 0 ) >= V
 

수식으로 정리

다음을 주어지는 값들을 활용해 수식으로 정리하면,
V <= ( A - B ) x (day - 1) + A
이와 같다. 즉, 구하고자 하는 day를 등식으로 세우면,
day >= ( V - B ) // ( A - B )
 
따라서, 달팽이가 정상에 도달하는 과정을 주어지는 값들로 수식으로 정리해
정상에 오르는 데 걸리는 일 수를 구해냈다.

---

솔루션 코드 작성

# 달팽이 는 올라가고 싶다

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

# day 변수 초기화
day = 0

# 수식으로 day 도출
if( (V - B) % (A - B) == 0):
  day = (V-B) // (A-B)
else:
  day = (V-B) // (A-B) + 1

print(day)

---

마치며

이번 문제는 한번에 해결해내지 못했다.
개인적으론 어려웠던 문제였다.
 
첫 접근 솔루션은 무한 반복문을 통해
주어지는 A, B를 통해 나무 막대 V 정상을 등산하는 데 며칠이 걸리는 지 1일부터 하나씩 체크해 정상에 오른
일 수를 구하는 솔루션을 채택하고
코드로 구현했다.
아래는 다음 솔루션으로 작성한 코드이다.

day 변수 초기화
day = 0

# 하루 달팽이 이동거리 초기화
total_len = 0

# 나무 막대 오르는 데 걸린 시간
while True:
   day += 1

# 아침 이동
   total_len += A 
   if(total_len >= V ):
     break

   # 져녁 이동
   total_len -= B



 print(day)

While True 문으로
day 변수 값을 +1 씩 증가해가며
달팽이가 낮에는 +A 미터 이동
정상에 도달하지 않았다면, -B 미터 이동시켜
매일의 달팽이 나무 막대에서의 이동거리를 측정했다.

조건연산을 통해 달팽이가 나무 막대 V에 도달했는지
낮에 +A 만큼 이동 후 체크해
최종적으로 정상에 도달한 일 수를 구해냈다.

하지만
백준 컴파일러 결과에선 시간초과가 나왔다.
시간 제한이 모든 더미 데이터에 대해서
2.5초 이하였다.
문제에선, 나무막대 길이가 1,000,000,000 까지 허용된다.
허용되는 데이터의 범위가 크므로
O(n)으로 작성한 위 코드는 입력 데이터로 큰 수가 주어지면 2.5초를 초과하여 "시간 초과" 결과를 주었다.
(실제로 시간을 측정하면, 5분 정도 걸릴 듯 하다.
어마 무시한... 비효율)

즉,
이번 문제는 허용되는 데이터의 범위가
압도적으로 크므로, O(n)으로 작성한 코드는
시간 초과라는 결과를 초래했다.


그러면, (이번 문제는 이렇게 솔루션을 마련했다.)
이번 문제는 O(n) 보다 효율성이 좋은
솔루션 코드를 작성해야만 문제 상황을 해결할 수 있다.
즉, 반복문을 사용하지 않은 코드로
나무 막대 정상을 오르는 데 걸리는 시간을 구해야한다.

어떤 데이터가 주어져도 올바른 값을 제공하는 수식을 세워 주어지는 데이터 값으로
정상에 오르는 데 걸리는 시간을 구해내는
이번 솔루션을 채택하여 문제를 해결해냈다.


이번 문제를 통해 배운점
지금까지 O(n) 으로 작성된 코드는 "언제나" 효율적이라고 생각했다.
하지만..
이번 문제를 풀어봄으로써 그러한 편견을 완벽하게 뿌술 수 있었다 ㅋㅋ
O(n) 은 1차 함수 그래프를 보면,
데이터가 압도적으로 커질수록 코드 효율이
떨어진다.
즉, 데이터가 압도적으로 큰 상황에선 O(n) 코드는 불리한 결과를 제공한다.
데이터가 큰 상황 속, O(n) 보단, 효율성이 좋은 솔루션을 채택해 유리한 결과를 만들어야 한다는 점을 깨닫게 되었다.

정리해서, 주어지는 데이터의 크기에 따라
문제 상황에 유리한 결과를 마련할 수 있는
솔루션을 채택해야 되는 것을 배울 수 있었다.
(이제 나도, 내가 처한 상황에서, 적합한 효율로 코드를 작성할 수 있겠다 ㅎㅎ)