[문제] 백준 2869 달팽이는 올라가고 싶다

* 백준 단계별로풀어보기- 기본수학 1 편

* 출처: www.acmicpc.net/problem/2869

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

엄청 쉽다고 생각했는데, 이 문제의 핵심은 시간 초과였다.

 

원래 풀려고 했던 방법은 아래와 같지만, 시간초과이다.

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 NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(in.readLine());
		
		int A = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		int V = Integer.parseInt(st.nextToken());
		
		int day = 0;
		int sum = 0;
		while(sum<V) {
			sum = sum+ A;
			day++;
			if(sum>=V) break;
			sum = sum - B;
		}
		
		System.out.println(day);
	}
}

 

그래서 풀이 법을 참고 했다.

 

정상에 올라가는 순간, 달팽이는 미끄러지지 않으므로 낮에 도착한다는 것을 알 수 있다.

즉, 낮을 x라고 한다면 밤은 x-1이다. 

 

A * x - B( x-1) = V 이므로 x = (V-B) / (A-B)임을 알 수 있다.

 

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 NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(in.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++;
        
		System.out.println(day);
	}
}