문제

https://www.acmicpc.net/problem/2869

조심할 것

이 문제는 반복문으로 풀게 될 경우 다음과 같은 슈도 코드가 나오게 될것이다.

하지만 이 알고리즘은 예제 3번의 경우에는 하루에 1칸식 이동하게 되므로 9억번 이상을 반복하기 때문에 9초를 넘어가게 된다.

그래서 반복문이 아닌 다른 방법으로 풀어야 된다.

설명

1차 공식

이 문제를 해결 하기 위해서는 문제를 꼼꼼히 읽어봐야 된다.
먼저 밑줄 친 부분을 보자

달팽이가 고정된 나무막대를 낯동안 A미터 올라가고 밤에는 B미터로 미끄러 진다.

이를 그림으로 표현하면 아래와 같다.

총 거리를 하루동안 이동한 거리로 나누면 걸리는 날이 나오게 된다.

이를 공식으로 표현하면 다음과 같다.

하루동안 움직이는거리는 (moving-sliding)이며 이걸 총 거리(distance) 로 나누어 다시 표현해보자

위 공식을 이용하여 예제1을 구해보자

하루동안 이동한 거리가 2미터이고 미끄러진 거리는 1미터 총 거리는 5미터인 경우 4일이 걸린다

하지만 위 식에 대입하면 아래와 같이 4가 나오지 않고 5가 나오게 된다.

디버깅(1차)

이는 문제에서

이 부분을 고려하지 않았기 때문이다.

우리가 구한 달팽이는 정상에 올라갔지만 다시 미끄러졌기 때문에 5일이 걸렸다.

우리는 정상에 올라간 후 미끄러지지 않는 것을 생각하며 구해야 된다.!

즉 달팽이는 아래와 같이 움직여야 된다.

총 거리에 미끄러진 거리를 미리 빼줘야 된다.
이를 다시 계산해 보면 다음과 같이 식을 수정해줘야 된다.

디버깅(2차)

또한 위 식은 거리가 딱 나올때 인 경우다
즉 2 1 5 인 경우 4가 나오지만

3 1 6 인 경우 에는 나머지가 존재하기 떄문에 결과값에 +1을 해줘야 된다.

즉 다음과 같은 경우에 위 공식으로 계산이 되어야 된다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class J2869 {
    public static void main(String[] args) throws IOException {
        BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
        String [] input = buffer.readLine().split(" ");

        int moving = Integer.parseInt(input[0]);
        int sliding = Integer.parseInt(input[1]);
        int distance = Integer.parseInt(input[2]);

        int result;

        if((distance - sliding) % (moving - sliding) != 0 ){
            result = (distance - sliding) / (moving - sliding)+1;
        }
        else result = (distance - sliding) / (moving - sliding);
        System.out.println(result);
    }
}