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

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

 

문제

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

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

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

 

입력

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

 

출력

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

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main (String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(reader.readLine(), " ");

        int morning = Integer.parseInt(token.nextToken());
        int afternoon = Integer.parseInt(token.nextToken());
        int tree = Integer.parseInt(token.nextToken());

        int snail = 0;
        int days = 0;

        while (snail < tree) {
            days += 1;
            snail += morning;
            if (snail >= tree) { // 낮에 이미 도달했으면
                break;
            }
            snail -= afternoon;
        }

        System.out.println(days);
    }
}

 

풀이

현재 달팽이가 위치하는 위치와 지난 날을 구하는 snail, days 변수를 선언해두고 while으로 하루씩 돌리면서 계산한다.

이렇게 하면 예제 모두 성공이지만, 제출을 하면 시간 초과가 난다. 계산 시간을 개선해야 한다.

 

챗지피티한테 정답 코드 말고 힌트를 좀 달라고 했더니, 다음과 같은 힌트를 주었다.

 

개선한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main (String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(reader.readLine(), " ");

        int morning = Integer.parseInt(token.nextToken());
        int afternoon = Integer.parseInt(token.nextToken());
        int tree = Integer.parseInt(token.nextToken());

        // 마지막 날에는 밤에 미끄러지지 않는다는 조건이 제일 중요
        // 전체 변수 기준을 마지막 날을 제외하도록 한다.

        // 달팽이가 도달해야 하는 높이 tree - morning
        int goal = tree - morning;

        // 하루에 올라가는 높이
        int day = morning - afternoon;

        // 총 높이 / 하루치 + 마지막 날
        System.out.println(goal / day + 1);
    }
}

 

근데 이렇게 했더니 두번째 예제에서 하루가 부족하게 계산되었다. 코드 중간 중간에 로그를 찍어 확인했더니, 정수 나눗셈이라 소수점 이하가 버려져서 제대로 계산이 되지 않는 것이었다. 그래서 나머지가 발생하면 +1을 하도록 수정했다.

 

최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main (String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(reader.readLine(), " ");

        int morning = Integer.parseInt(token.nextToken());
        int afternoon = Integer.parseInt(token.nextToken());
        int tree = Integer.parseInt(token.nextToken());

        // 마지막 날에는 밤에 미끄러지지 않는다는 조건이 제일 중요
        // 전체 변수 기준을 마지막 날을 제외하도록 한다.

        // 달팽이가 도달해야 하는 높이 tree - morning
        int goal = tree - morning;

        // 하루에 올라가는 높이
        int day = morning - afternoon;

        // 총 높이 / 하루치 + 마지막 날
        System.out.println((int)Math.ceil((double) goal / day) + 1);
    }
}

 

결과