[P&B] #66 BAEKJOON 2869

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

문제 설명

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

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

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

 

입력

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

 

출력

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

 

나의 문제 풀이 코드

import java.io.*;
public class bj2869 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());

        // 마지막 날에는 A만큼 올라가지 않으므로 V - A로 나누어 올림한 값을 출력합니다.
        int day = (int) Math.ceil((double) (V - A) / (A - B)) + 1;

        bw.write(String.valueOf(day));
        bw.flush();
    }
}

문제 풀이 코멘트

처음 이 문제를 보았을 땐 생각보다 어렵지 않은데? 라는 생각을 하며 아래의 코드로 풀었습니다.

import java.io.*;
public class bj2869 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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 day = 0;
        int sum = 0;
        while (sum < V){
            day++;
            sum += A;
            if (sum >= V)
                break;
            sum -= B;
        }
        
        bw.write(String.valueOf(day));
        bw.flush();
    }
}

하지만 이 코드를 제출하면 시간 초과가 발생했습니다. 문제는 똑같이 풀리지만 메서드를 어디서 어떻게 사용하느냐에 따라 시간 복잡도가 달라집니다.

정답 풀이에서 사용한 Math.ceil을 설명하자면 다음과 같습니다.

Math.ceil 함수 :

• (V - A)는 나무 막대의 총 높이에서 첫 번째 날에 올라가는 높이 A를 뺀 값입니다. 이는 나무 막대에서 첫 번째 날 이후에 올라가야 하는 높이를 나타냅니다.
• (A - B)는 하루에 올라가는 높이와 밤에 미끄러지는 높이의 차이입니다. 이 값은 하루에 얼마나 높이를 올라갈 수 있는지를 나타냅니다.
• (V - A) / (A - B)는 나무 막대의 총 높이를 첫 번째 날부터 하루에 올라갈 수 있는 높이로 나눈 것으로, 결과값은 첫 번째 날 이후 몇 일이 걸리는지를 나타냅니다.
• Math.ceil 함수는 이 값을 올림한 정수로 변환합니다. 즉, 소수점 이하가 존재하는 경우에도 다음 날로 올림하여 최소한의 일수를 구합니다.
• 마지막으로 + 1을 더하는 이유는 첫 번째 날을 포함하기 위함입니다.

결과적으로, day 변수에는 나무 막대를 모두 올라가는데 필요한 최소한의 날짜가 저장되며, 이 값을 출력합니다. 이 코드는 반복문 없이 Math.ceil 함수를 활용하여 간결하고 빠르게 문제를 해결이 가능합니다.