[백준 알고리즘][자바] 2869번 : 달팽이는 올라가고 싶다

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

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

안녕하세요. 이번 포스팅은 2869번: 달팽이는 올라가고 싶다입니다.

달팽이가 나무 막대를 모두 올라가는 데 며칠이 걸리는지 구하는 문제입니다.

첫째 줄에 입력 받는 세 정수 A, B, V는 다음과 같습니다.

• A = 달팽이가 낮동안 올라가는 길이(미터)
• B = 달팽이가 밤동안 미끄러지는 길이(미터)
• V = 나무 막대기의 길이(미터)

이때 올라가는데 며칠이 걸리는지 출력합니다.

이 문제의 주요 포인트는 두 가지입니다.

1. 정상에 올라간 후엔 미끄러지지 않는다.
2. 시간제한

정상에 올라간 후엔 미끄러지지 않는다. 이것에 대한 예를 들어 봅시다.

예제 1번과 같이 A = 2, B = 1, V = 5 일 때 AX - BX = V로 단순 계산했을 때는 x = 5입니다.

하지만, 차례대로 진행해보면

• 1일차 낮 = 2m
• 1일차 밤 = 1m
• 2일차 낮 = 3m
• 2일차 밤 = 2m
• 3일차 낮 = 4m
• 3일차 밤 = 3m
• 4일차 낮 = 5m

이렇게 4일차 낮에 정상인 5m를 올라갔기 때문에 밤에는 내려오지 않고 4일 차에 끝나게 됩니다.

여기서 두 번째 포인트 시간제한

낮과 밤사이에 정상에 올랐는지 확인하며 X를 1씩 늘려가며 반복문을 쓰게 되면 제한 시간 0.15초 안에 풀 수 없습니다.

따라서 X가 어떠한 공식에 의해 바로 도출이 되어야 합니다.

여기서 문제는 달팽이가 낮에 정상에 도착했을 때는 밤을 계산하지 않는 것입니다. 그렇다면 기준을 낮으로 두면 됩니다.

• 1일차 낮 = A
• 1일차 밤 = A - B
• 2일차 낮 = A - B + A
• 2일차 밤 = A - B + A - B
• 3일차 낮 = A - B + A - B + A
• 3일차 밤 = A - B + A - B + A - B
• 4일차 낮 = A - B + A - B + A - B + A
• 4일차 밤 = A - B + A - B + A - B + A - B

여기서 낮만 도출해보겠습니다.

• 1일차 낮 = A
• 2일차 낮 = A - B + A
• 3일차 낮 = A - B + A - B + A
• 4일차 낮 = A - B + A - B + A - B + A
• X일차 낮 = (A - B) * (X - 1) + A

이해가 되시나요?

• V = AX - A - BX + B + A
• V = X * (A-B) + B
• V - B = X * (A-B)
• X = (V - B) / (A - B)

여기서 계산한 X 값이 소수점이 나왔을 경우에는 소수점만큼 더 가야 하기 때문에 다음날까지 되어야 한다는 뜻입니다.

따라서 Math.ceil()을 통해 올림을 해주도록 합니다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] ABV = br.readLine().split(" ");
		
		double A = Integer.parseInt(ABV[0]); // 낮동안 올라가는 길이
		double B = Integer.parseInt(ABV[1]); // 밤동안 미끄러지는 길이
		double V = Integer.parseInt(ABV[2]); // 나무 막대의 길이
		
		int X = (int) Math.ceil((V - B) / (A - B)); // 올라가는 데 걸리는 일 수
		
		bw.write(String.valueOf(X));
		
		br.close();
		bw.flush();
		bw.close();
	}
}