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

문제

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

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

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

입력

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

2 1 5

출력

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

4

 

 

내 코드

이게 까다로운 점은 마음같아선 그냥 하루에 올라가는 길이 즉, up - down으로 목표 거리를 나눠주고 싶지만, 대부분의 경우, 마지막 날에는 낮에 올라가는 도중에 목표지점에 도달하는 것이 현실이라 생각과는 거리가 멀다는 점이다.

예를 들어 낮에 9 미터 올라가고 밤에 8미터 미끄러지는 데, 목표지점이 5미터라면 이미 첫날 낮에 도달했을 것이다.

따라서 이러한 과정을 그대로 코드로 옮긴 것이 첫 제출이었다.

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int up = sc.nextInt();
    int down = sc.nextInt();
    int goal = sc.nextInt();
    int count = 1;
    
    while (goal - up > 0) {
      goal -= (up - down);
      count++;
    } 
    System.out.println(count);
  }
}

하루가 지나가는 것을 count로하고 첫째날 낮에 올라간 만큼 목표 거리에서 up을 빼줬을 때 0보다 크다면, 도달하지 못했으니 하루 동안 간 거리 up - down을 빼주고 count를 올려 둘쨋날로 만들어준다. 둘쨋날 낮에 up만큼 빼고 남은 거리가 아직도 0보다 크다면 다시 하루를 보내준다. 이런 방식으로 코드를 짜면 답은 잘 나오지만 시간 제한은 0.15초라서 시간초과가 떠버린다.

 

그렇다면 이렇게 하루하루를 재현하는 코드는 시간 안에 불가능하다. 완전히 다른 접근 방식이 필요한데, 나는 목표 지점에 도달하는 데 걸리는 날짜를 n으로 해줬을 때 goal이 n번째 날 낮에 도착하려면 (n - 1)번째 날에 도달하는 최고 지점보다는 goal이 높아야 하고 n번째 날에 도달하는 최고 지점(goal에서 멈추지 않는다고 가정)보다는 같거나 낮아야 한다고 조건을 걸었다. 이 조건을 수식으로 쓰면

(n - 2)(up - down) + up < goal <= (n - 1)(up - down) + up 이렇게 되고

우리가 알고 싶은 것은 n이므로 n 중심으로 조건문을 바꿔주면

(goal - up) / (up - down) + 1 <= n < (goal - up) / (up - down) + 2 

이렇게 된다. 

우리는 이 범위 안에 있는 n만 구하면 되므로 반복문을 돌리던 아까의 방식보다 훨씬 실행이 짧아진다.

그런데 n은 정수기 때문에 (goal - up) / (up - down) 의 결과가 정수냐 소수냐에 따라 n의 값이 달라지므로 조건에 따라 결과를 나눠 출력했다.

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int up = sc.nextInt();
    int down = sc.nextInt();
    int goal = sc.nextInt();

    // (n - 2)(up - down) + up < goal <= (n - 1)(up - down) + up
    // (n - 2)(up - down) < goal - up <= (n - 1)(up - down)
    // n - 2 < (goal - up) / (up - down) <= n - 1
    // n < (goal - up) / (up - down) + 2 && n >= (goal - up) / (up - down) + 1
    
    if ((goal - up) % (up - down) == 0) {
      System.out.println((goal - up) / (up - down) + 1);
    } else {
      System.out.println((goal - up) / (up - down) + 2);
    }
  }
}