[백준] 2869번 달팽이는 올라가고 싶다(JAVA)

문제

- 달팽이는 높이가 V미터인 나무 막대 올라감

- 낮에 A미터 올라갈 수 있음

- 밤에 B미터 미끄러짐

- 정상에 올라가면 미끄러지지 않음

- 달팽이가 나무 막대를 모두 올라가는데 며칠 걸리는지 구하기

 

해결방법

이 문제는 V미터에 도달할 때까지 단순히 A를 더해주고 B를 빼주면 시간초과를 만나는 문제이다. 따로 계산할 수 있는 수식이 필요하다고 생각했었기 때문에 달팽이가 움직이는 것을 생각해보았다. 달팽이는 정상에 도달할 때 N번 올라간다면 N-1번 내려오는 과정이 필요하다. 마지막 올라갔을 때 정상에 도달하면 내려오지 않아도 되기 때문에 N-1번 내려오는 과정이 필요한 것이다. 

count = (V - A) / (A - B);

그래서 마지막으로 올라갈 A미터를 남겨두고 하루에 움직일 수 있는 양(A-B)만큼 움직이는 횟수를 구해주고

count * (A - B) + A >= V

하루에 움직일 수 있는만큼 움직인 뒤 A만큼 더 올라갔을 때, 목표 지점에 도달한다면 마지막에 A만큼 더 올라간 1회만 더 더해주면 되는 것이다.

count * (A - B) + A < V

하지만, 이렇게 올라갔는데 목표 지점에 도달하지 못했다면 다시 내려왔다가 한 번 더 올라가야 되기 때문에 2회를 더해주어야 한다.

 

코드

import java.io.*;
import java.util.*;

class Main {

    public static void main(String[] args) throws Exception {
        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());		// 최종 도달해야 할 높이
        int count = 0;
        int move = A - B;					// 하루동안 움직인 양

        count = (V - A) / move;     					// 마지막으로 올라갈 것 남겨두고 하루 움직일 수 있는 양만큼 움직이기
        if(count * move + A >= V) System.out.println(count + 1);    	// 움직일 수 있는만큼 움직이고 한 번 더 올라갔을 때, 나무 높이에 도달 했다면 한 번 더 올라간 것만 카운팅 더 해줌
        else System.out.println(count + 2);     			// 해당 높이에 도달하지 못했다면 한 번 더 움직여야 하므로 한 번 더 올라간 것 + 그 다음 내려왔다 또 올라간 것 카운팅 해줌

        br.close();
    }
}