[Codility] Lesson3. FrogJmp - 문제풀이

Description

정수 X, Y, D가 주어졌을 때 위치 X에서 Y보다 크거나 같은 최소 점프 수를 반환합니다.

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:

class Solution { public 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 = 40after the second jump, at position 10 + 30 + 30 = 70after 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.

Solution 1. Math

public int solution(int X, int Y, int D) {
    int result = (Y-X)/D;
    int n = (Y-X)%D > 0? 1 : 0;
    return result+n;
}

반복문으로 실제로 계산하지 않아도 최소 점프수를 수식을 통해 바로 계산하여 시간복잡도 N(1)의 솔루션이 나올 수 있습니다.

Reference

FrogJmp coding task - Learn to Code - Codility