스파르타 알고리즘 트랙 문제 1일차 - 3 #2869 달팽이는 올라가고 싶다

문제

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

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

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

 

해결 과정

처음에는 단순하게 답이 나올 때까지 반복문을 사용해 계산하는 코드로 작성하였다.

import java.io.*; import java.util.*; public class Main {     public static void main(String[] args) throws IOException {         int ans = 0;         Scanner a = new Scanner(System.in);         int up = a.nextInt();         int down = a.nextInt();         int total = a.nextInt();         while(true) {             ans++;             total = total - up;             if (total <= 0) {                 break;             }             total = total + down;         }         System.out.println(ans); }}

그러나 돌아온 제출 결과는 "시간 초과"였다. 문제를 해결하는 데 너무 많은 시간을 사용한 것이었다.

실제로 위의 방법을 사용할 경우 O(n)의 시간복잡도를 갖게 된다. 그렇지만 위 문제를 O(1)의 시간복잡도를 갖는 코드로 해결할 수 있음을 알게 되었다.

 

새로운 코드 작성 전 약간의 수학적 계산이 필요했다.

달팽이가 정상에 도달하기 위해서는 직전에 A미터 올라가는 행위가 필요하다. 또한 A미터를 올라 정상에 다다를 경우 B미터 미끄러지는 행위는 발생하지 않으므로, 달팽이가 나무 막대를 올라가기 위해 걸리는 시간을 X라 할 경우, 아래와 같은 식이 성립한다.

V <= A * X - B * (X-1) V <= A * X - B * X + B V - B <= (A - B) * X  (V - B)/(A - B) <=  X

결과적으로 X >= (V - B)/(A - B)를 만족하는 가장 작은 자연수 X값을 구하는 코드를 작성하면 되는 것이었다.

import java.io.*; import java.util.*; public class Main {     public static void main(String[] args) {         int ans = 0;         Scanner a = new Scanner(System.in);         int up = a.nextInt();         int down = a.nextInt();         int total = a.nextInt();         if((total-down)%(up-down)!=0;)             ans = (total-down)/(up-down)+1;         else             ans = (total-down)/(up-down));         System.out.println(ans); }}

이렇게 제출한 코드는 시간 초과 없이 정답임을 확인받을 수 있었다.