[코테]코딜리티 - FrogJmp

문제

문제 요약

• 개구리 위치 x에서 y까지 가기 위해서 고정된 범위인 d만큼 점프를 한다.
• 이 때, x가 y 이상이 되려면 점프를 몇번해야하는지 구해야한다.
• 1 <= X, Y, D <= 1,000,000,000의 범위를 가진다.

문제 분석

나는 다음과 같이 문제를 분석했다.

• 범위가 10억 이하이다.
• 최악의 경우 X = 1, Y = 10억, D = 1일 때 반복을 수행하면, 10억번을 수행해야한다.
• 시간 제한을 고려하여 시간복잡도를 단축해야한다.
• 먼저 Y - X = n의 식을 세우고, 다시 n / D를 통해 값을 나눈다.
• 나눠진 값을 Math.ceil() 함수를 이용하여 올려주면 X가 Y 이상이 되기 위한 값이 나온다.
• 이 식으로 수행하면 입력 값의 차이가 발생하더라도 연산의 횟수는 항상 고정이다.
• 즉, 시간복잡도는 O(1)이다.

슈도코드

// Y - X를 하고 값을 저장한다.
// 저장된 값을 D로 나눈다.
// 나눈 값을 double형으로 형변환하여 저장한다.
// Math.ceil()을 이용해 올림한다.
// 결과를 반환한다.

구현코드

class solution{
	public static int solution(int X, int Y, int D){
    	int n = Y - X;
        double m = (double) n / D;
        int answer = (int) Math.ceil(m);
        
        return answer;
    }
}

부가설명

while (X < Y) {
    X += D;
    if (X >= Y) {
        answer = X;
        break;
    }
}

처음에는 위와 같이 반복을 수행하며 X에 D를 누적하는 방법으로 수행하려 했다. 하지만 이렇게 수행 할 경우 시간복잡도는 O((Y-X) / D)가 된다. 이 말은 입력 값에 따라 연산 횟수가 달라질 수 있다는 것이다.
이러한 이유로 시간복잡도가 고정되어 있는 구현코드를 사용하였다.