[Time Complexity] ForgJmp

알고리즘 태클 열렬히 환영합니다~

지적 부탁드립니다~~

[Time Complexity] ForgJmp

URL : https://codility.com/programmers/lessons/3-time_complexity/frog_jmp/

개구리가 길의 한쪽편에서 다른쪽편으로 가려고 합니다.

개구리는 현재 X위치에 있고, Y위치나 Y보다 멀리 가려고 합니다.

개구리는 항상 D만큼 점프할 수 있습니다.

아래와 같은 함수를 작성해 봅시다:

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

정수 X, Y, D가 주어졌을 때,

X에서 뛰어서 Y 이상의 위치에 도달하는데 최소 몇 번을 뛰어야 하는지 구하는 함수입니다.

예를 들어 :

X = 10

Y = 85

D = 30

위와 같이 주어졌다고 하면 함수는 3을 반환해야 합니다.

- 첫번째 점프 후 : 10 + 30 = 40

- 두번째 점프 후 : 10 + 30 + 30 = 70

- 세번째 점프 후 : 10 + 30 + 30 + 30 = 100

제약조건 :

- X, Y, D는 1~1,000,000,000 범위의 정수입니다.

- X ≤ Y 입니다.

- 최악의 경우 시간복잡도는 O(1) 입니다.

- 최악의 경우 공간복잡도는 O(1) 입니다.

C언어 100% 점수 획득 코드

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

int result;

if (0==((Y-X)%D))

return (Y-X)/D;

else 

return (Y-X)/D + 1;

}

Y-X 거리를 D만큼씩 점프해서 이동합니다.

따라서 Y-X / D가 최소 점프 횟수가 됩니다.

그러나 이 값들이 모두 정수이기 때문에, D로 나누어 떨어지지 않는 경우 오차가 발생합니다.

문제의 예를 보면, Y-X는 75이고, 이를 30으로 나누면 2.5가 되는데,

정수 연산의 특성상 소수점 아래는 버려버리기 때문에 2가 결과로 나옵니다.

올림을 사용할 수도 있지만, 저는 나누어 떨어지는 경우와 그렇지 않은 경우로 나누어

나누어 떨어지지 않을 경우 결과값에 +1을 처리해 주었습니다.