백준 - 2869번 달팽이는 올라가고 싶다.

코드

---

이 문제는 반복문을 이용해서 하루하루를 계산하게 되면 시간초과가 발생합니다.

 

A가 2, B가 1일 때 V까지 도달하려면 기본적으로 10억번의 반복문이 돌아야하고, 그 안에 각종 연산자들까지 포함한다면  시간제한 0.25초를 넘어서게 됩니다.

 

그러면 반복문을 사용하지 않고 푸는 방법으로는 단순 식을 세워서 계산하는 방식이 있습니다.

 

일단 하루를 온전히 보낸다(낮과 밤 모두 보냄)는 가정하에 오를 수 있는 높이는 A - B 입니다.

 

그런데, 문제를 잘보면 정상에 오르는 순간 미끄러져 내려가지 않는다고 합니다. 이 부분을 주의해야합니다.

 

예를 들어, V가 5이고 A는 3, B는 2인 경우 하루에 오를 수 있는 높이는 1입니다. 그러면 단순히  5 / 1 = 5일로 계산이 됩니다. 그런데 차근차근 한번 살펴 봅시다. 

 

• 첫째날 :  3 - 2 = 1
• 둘째날 : (1 + 3)  - 2 = 2
• 셋째날 : (2+3)  -> 낮시간 동안 정상에 도착

단순히 올라가고 내려가는 것을 하나로 생각해서 계산하면 5일, 따로따로 생각하면 3일이라는 시간이 나옵니다. 정답은 3이므로 단순히 낮밤하나를 통째로 생각하면 정답을 구할 수 없습니다.

 

전체 높이에서 마지막 날 낮에 올라갈 수 있는 높이를 제외하고 나머지 높이를 낮밤 높이로 나누어주면 전체 걸리는 시간을 구할 수 있습니다.

 

package baekjoon;

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

public class No_2869 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		int A = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		int V = Integer.parseInt(st.nextToken());

/**
 *      while문으로 하나하나 돌리면 시간초과 발생 (10억 이상의 연산이 발생할 수도)
 *      int cur = 0;
 * 		int day = 0;
 *
 * 		while (true) {
 * 			cur += A;
 * 			day++;
 * 			if (cur >= V) {
 * 				break;
 *                        }
 * 			cur -= B;* 		}
 * 		System.out.println(day);
 */
		// 하루에 올라갈 수 있는 높이
		int one = A - B;
		// 마지막 날에 밤까지 가지 않고 낮에 등반하는 경우가 발생하므로 전체 높이에서 낮에 올라가는 높이 제외
		int remain = V - A;
		// 남은 높이 / 하루 높이 -> 등반하는데 걸리는 날짜 + 마지막 날 낮 등반한 것 하루
		int day = remain / one + 1;
		// 딱 떨어지지 않으면 하루 더 올라가야 하므로 1 추가
		if (remain % one != 0) {
			day++;
		}
		System.out.println(day);
	}

}