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

2869번 문제

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V 미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A 미터 올라갈 수 있다.
하지만, 밤에 잠을 자는 동안 B 미터 미끄러진다.
또, 정상에 올라간 후에는 미끌어 지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는 지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, V 가 공백으로 구분되어서 주어진다.
(1 ≤ B < A ≤ V ≤ 1,000,000,000)

출력

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

🗝️포인트

• 처음 생각엔 반복문을 통해 높이에 덧셈/뺄셈을 하여 높이 값이 0이 나오면 출력되도록 구현하였으나... 반복문으로는 0.25초(250ms) 이내에 통과가 불가능 했다.

• 해결 방안
  높이를 실제 하루에 이동하는 값 만큼 나눠주면, 전체 이동한 날이 나오게 된다. Ex) 높이 5M를 하루 2M(낮 이동 - 밤 미끄러짐) 이동 시 5/2하여 몫이 2라는 값이 나오게 된다. 즉 5M를 올라가는데 걸린 날짜가 2일이 걸렸다는 의미이다.

  하지만, 이 식에는 오류가 있는데 먼저, 거리가 남아서 정상에 도달하지 못했다는 점이다.즉, 다음날 낮 이동한 시간에 정상에 올라가게 된 경우의 수를 빼고 생각한 것이다.

  그리고, 낮에 정상에 올라간 경우, 정상에서는 미끄러지지 않기 때문에 밤에 떨어지는 것을 고려하지 않는다.(높이 = 높이 - 미끄러짐)

  위의 경우의 수를 고려하면, (높이 - 미끄러짐)이 하루 이동 거리에 딱 맞춰 이동이 끝나는 경우(나머지가 0인 경우)에는 원래 몫을 출력하면 되고, 하루 이동 거리보다 작은 거리가 남은 경우 하루가 더 걸리는 것으로 고려해줘야 한다.

  다시 정리하면 높이 - 미끄러짐의 의미는 다음날 낮까지 정상에 도착하는 지를 보겠다는 의미이다. 따라서 위 값에 하루 이동량을 나누어 주어 나머지가 0이게 되면, 다음날 낮에 정상에 도착했음을 의미하고, 나머지가 있는 경우에는 다음날 저녁에 한번 더 미끄러지게 됨을 의미하여 하루를 더해줘야 한다.

제출 답안

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 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());

		br.close();
		int day = (V-B)/(A-B);
		if((V-B) % (A-B) != 0) day++;

		System.out.println(day);
	}
}

참조 포스팅