Codility - Frog Jmp // C++

문제

 

A small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to a position greater than or equal to Y. The small frog always jumps a fixed distance, D.

Count the minimal number of jumps that the small frog must perform to reach its target.

Write a function:

int solution(int X, int Y, int D);

that, given three integers X, Y and D, returns the minimal number of jumps from position X to a position equal to or greater than Y.

For example, given:

X = 10 Y = 85 D = 30

the function should return 3, because the frog will be positioned as follows:

• after the first jump, at position 10 + 30 = 40
• after the second jump, at position 10 + 30 + 30 = 70
• after the third jump, at position 10 + 30 + 30 + 30 = 100

Write an efficient algorithm for the following assumptions:

• X, Y and D are integers within the range [1..1,000,000,000];
• X ≤ Y.

 

개구리의 현재 위치 X, 목표 위치 Y, 한 번에 뛸 수 있는 거리 D가 주어진다.

이 때, 개구리가 Y까지 가기 위해 몇 번을 뛰어야 하는지를 구하는 문제이다.

---

 

풀이

 

처음엔 단순히 반복문을 통해 계산을 했지만, Y의 값이 크고 D 값이 작을 때 시간 초과가 많이 발생했다.

 

따라서 반복문을 사용하지 않고 계산을 하는 방법을 생각해 봤는데, 결국 개구리가 가야하는 거리는 Y-X가 된다.

 

Y-X를 D로 나눴을 때, 나머지가 없다면 그 몫만큼만 점프를 하면 도착할 수 있게 되고 나머지가 있다면 한 번 더 뛰어야 갈 수 있게 된다.

 

---

 

코드

int solution(int X, int Y, int D) {
    if((Y-X) % D == 0)
        return (Y-X) /D;
    else
        return (Y-X) / D + 1;
}