단계별 문제 풀이3. 2869번 <달팽이는 올라가고 싶다>

처음 문제를 보고, 단순한 객체 구현만으로 쉽게 풀 수 있을 줄 알았다....

ㅎㅎ...시간 제한이 0.15초에 입력 범위가 10000000000이라는 사실을 간과했다. 

단순 객체 구현으로 풀면 10000% 시간 초과가 나올 것이 뻔했기에 문제를 수학적으로 접근하는 것이 필요했다.

달팽이는 낮에 A 만큼 올라가고, 밤에 B만큼 떨어진다. 

즉, 전체 높이를 (A-B)만큼 나눈 몫이 정답인가? 했지만 한 가지 조건이 더 있다. 

한번 달팽이가 정상에 도달하면, 달팽이는 미끄러지지 않는다. 

정리하면, 달팽이는 하루에 (A-B)씩 V 높이를 오르는 것이 아닌, (A-B)씩 V - B 높이를 오르는 것이다.

또한 높이와 달팽이의 속력을 나눈 나머지가 0이면, 나눈 몫이 정답이겠지만, 나누어 떨어지지 않는다면, 달팽이는 또 한번 미끄러질 것이고, +1만큼 더 올라야한다.

 

Code:

package com.choonham;

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

public class Main {
	public static void main(String[] args)  throws IOException {
		int days = 0;
		int[]  arrayA = new int[3];
		String[] inputValues;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		inputValues = br.readLine().split(" ");
		for(int n = 0; n< 3; n++) {
			arrayA[n] = Integer.parseInt(inputValues[n]);
		}
		if((arrayA[2]-arrayA[1])%(arrayA[0]-arrayA[1])!=0) {
			days = (arrayA[2]-arrayA[1])/(arrayA[0]-arrayA[1]) + 1;
		} else
			days = (arrayA[2]-arrayA[1])/(arrayA[0]-arrayA[1]) ;
		System.out.println(days);
		
	}
}