[백준/Java]Q2869

백준 알고리즘 8단계 기본 수학1 2869번 문제입니다.

---

Q. 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라가려고 한다.
    달팽이는 낮에 A미터를 올라가고 밤에 B미터 미끄러진다.
    달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

[입력]
- 세 정수 A, B, V가 공백으로 구분되어서 주어진다.

 

[조건]
- 1 ≤ B < A ≤ V ≤ 1000000000
- 정상에 올라간 후에는 미끄러지지 않는다.
- 시간제한 0.15초

 

풀이

이 문제에서 중요한 건 시간제한이 있다는 것과 정상에 올라간 후에는 미끄러지지 않는다는 조건이었다.

시간제한이 있기 때문에 반복문을 쓰지 않고 결과를 구해야 했다. 일단 단순히 봤을 때 (달팽이가 올라가야하는 높이) / (올라가는 거리 - 미끄러지는 거리)로 하면 되지 않을까 싶었다.

하지만 예제 출력값을 보면 알 수 있듯이 생각한 값이 정답이 아니었다.

x = 5 / (2 -1)

x = 5 (예제의 답은 4)

 

왜인지 그림을 그려봤다.

단순 식대로라면 5에서 2-1을 나누면 되는 것처럼 보이지만 실제로는 5에서 -1을 해줘야 했다. 왜냐하면 하루에 올라가는 거리(+2), 미끄러지는 거리(-1)를 돌려보면 3일째되는 날에 4에 도착한다.

4일째되는 날 +2 올라가지만 정상에 올라간 후에는 미끄러지지 않기 때문에 4로 마무리가 된다. 즉, 올라가야하는 높이에서 -1을 한 거리로 나눠야하는 결론이 나온다. 그런데 그림 오른쪽과 같이, 결과가 0으로 떨어지지 않는 경우((6-1)/(5-1))는 하루를 더 소모해야 하므로 +1을 해주어야 했다.

 

소스

package com.baek.algo;

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

public class Q2869 {

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

		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		int v = Integer.parseInt(st.nextToken());

		int day = (v - b) / (a - b);

		if(((v - b) % (a - b)) != 0) {
			day = day + 1;
		}

		System.out.println(day);

		bf.close();
	}
}