백준 알고리즘 | 2869번 문제: 달팽이는 올라가고 싶다

출처

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

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.
달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.
달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1

2 1 5

예제 출력 1

4

예제 입력 2

5 1 6

예제 출력 2

2

예제 입력 3

2 1 5

예제 출력 3

4

예제 입력 4

100 99 1000000000

예제 출력 4

999999901

알고리즘 분류

  • 수학

문제 풀이

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 {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            StringTokenizer input = new StringTokenizer(br.readLine(), " ");

            double a = Integer.parseInt(input.nextToken());
            double b = Integer.parseInt(input.nextToken());
            double v = Integer.parseInt(input.nextToken());

            System.out.println((int) Math.ceil((v - a) / (a - b)) + 1);
        }
    }
}

하루에 a만큼 오르고 b만큼 미끄러지기에, a에서 b를 빼면 하루에 오를 수 있는 높이가 나온다.

(a - b)

마지막날은 미끄러지지 않기 때문에 높이(v)에서 하루 오르는 만큼(a) 빼면 마지막날 전날에 오르게 되는 높이가 나온다.

(v - a)

그러면, “실제 올라야 할 높이"에서 “하루 올 수 있는 높이"를 나누면 며칠이 걸리는지 나오고, 마지막 날에도 오를 것이기에 하루(1)를 더하면 최종 걸리는 일수가 나온다.

이를 실제 값으로 구해보자.
입력 받은 “2 1 5” 이거라고 했을때,

a = 2, b = 1, v = 5

5 - 2 = 3 > 마지막날 전날에 오르게 되는 높이
2 - 1 = 1 > 하루에 오를 수 있는 높이
(5 - 2) / (2 - 1) = 3 > 올라가는 일수
3 + 1 = 4 > 올라가는 일수에 마지막 하루(1)를 더해서 최종 4일이 걸린다.



최종 수정 : 2022-04-03