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

문제 출처: https://www.acmicpc.net/problem/2869

문제

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

• 달팽이는 낮에 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 IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int A = Integer.parseInt(tokenizer.nextToken());
        int B = Integer.parseInt(tokenizer.nextToken());
        int V = Integer.parseInt(tokenizer.nextToken());

        // 하루의 이동거리 -> A - B
        int day = (V - B) / (A - B);

        if ((V - B) % (A - B) != 0) day++;

        System.out.println(day);
    }

}

• 처음에 단순히 올라가고 정상인지 확인한 다음 빼주는 방식으로 로직을 구성했을 때는 시간초과가 떴다.
• 고민 끝에 답을 얻지 못해 구글링한 결과, 논리를 발견할 수 있었다.
• 우선 달팽이는 하루에 A - B 만큼이 총 이동량이다. 예시 1번에서 2 1 5 일 때, 달팽이는 하루(낮+밤)에 총 이동량은 1이다.
• 쉽게 생각해서, 그 날의 최종 이동 거리에서 정상을 찍었는지, 안찍었는지를 판단해 주면 된다.
• 예시 1번 2 1 5에서 4일 동안 진행한 최종 위치는 4이다. 근데 이 경우는 낮에 이미 5를 찍고 왔다. 그래서 답은 4가 된다.
• 이를 판단하기 위해 V - B 까지의 이동 날 수를 계산한다.
• 예시 1번이 2 1 6이라면, 4일 동안 진행한 위치에서 하루를 더 가야한다.그래서 답은 5가 된다.