[JAVA / 자바] 백준 2869번 - 달팽이는 올라가고 싶다

문제

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

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

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

---

입력

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

---

출력

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

---

 

---

문제 접근 방법

달팽이는 낮에 올라가서 밤에 미끄러진다. 그렇다면 하루 동안 올라간 높이 = 올라간 높이 - 미끄러진 높이 가 된다. 그런데 이때 달팽이는 정상에 닿으면 미끄러지지 않고 오르기만 한다. 그렇다면 달팽이가 정상까지 올라가기 전날의 위치는 정상에서 달팽이가 낮에 올라갈 수 있는 높이보다 같거나 낮게 떨어져 있어야 한다. 달팽이가 정상에 오르기 전날이 가능한 최소의 높이는 v-a이고 달팽이가 하루에 오르는 순 높이는 a-b이다. 따라서 날짜를 계산할 때 하루 단위로 올라가는데 걸린 날을 계산하려면 하루 단위 오르는 높이에는 달팽이가 미끄러지는 높이도 포함이 되어있으므로 먼저 달팽이가 마지막 날 달팽이가 오르는 거리를 빼고 계산해준다(v-a: 왜냐면 달팽이가 마지막 날 얼마큼 오를지 모르기 때문에 마지막 날이 될 수 있는 최소한의 높이로 계산해주는 것이다.). 그럼 이 남은 높이를 달팽이는 며칠 동안 오를지는 하루 동안 달팽이가 오르는 높이인 (a-b)로 나누어주면 된다. 이때 조심해야 할 부분이 두 가지가 있는데 이 계산식( (v-a)/(a-b) )은 달팽이가 마지막 날 오를 수 있는 높이보다 적게 올라도 달팽이가 정상에 도달한다면 하루가 적게 계산된다. 따라서 위 계산식이 맞아떨어지지 않으면 하루를 결괏값에 더해주어야 하고 두 번째로, 달팽이가 마지막 날 오른 결과를 빼고 계산한 값이므로 마지막 날 하루를 결괏값에 더해주어 최종 결괏값을 도출해주면 된다.

---

JAVA 코드 풀이

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());
        
        int days = (v-a) / (a-b); // 달팽이가 정상에 오르기 전날까지의 날
        if((v - a) % (a-b) != 0) // 달팽이가 하루에 오르는 높이보다 정상까지의 높이가 짧을때
            days++;
        System.out.println(days+1); // 마지막날 오른 기록은 계산식에 포함되어있지 않으므로 출력에 1일을 더해준다.
    }
}

코드 실행 결과

---

후기

이번 문제는 시간제한 때문에 상당히 까다로운 문제가 되었다. 따라서 입력을 Scanner함수로 받으면 시간제한에 걸렸다.. 또한 반복문을 쓰면 시간제한에 걸리기 때문에 최대한 단순한 계산으로 만들어야 했다. 따라서 계산식을 만들었어야 하는데 계산식도 복잡하게 된 것 같다.. 머리가 조금 아픈 문제인 것 같다.

---

문제 원본

https://www.acmicpc.net/problem/2869