[Codility] 3. Time Complexity | FrogJmp 🐸

❓ Task

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 = 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.

💡 Solution

문제는 길~게 설명되어있지만 아주 간단한 1차 부등식으로 정리가 가능합니다.

a = 점프수
Y ≤ X+aD

∴ a ≥ (Y-X)/D

위 부등식을 활용하면 아주 간단한 코드가 완성됩니다!

class Solution {
	public int solution (int X, int Y, int D){
    	return (int) Math.ceil((Y-X)/(D*1.0));
	}
}

💬 Note

1. 계산 결과의 소수점을 보존하기 위해 double로 변환하고자 1.0을 곱해주었습니다. 명시적 형변환을 할 수도 있습니다.

Math.ceil((Y-X)/(D * 1.0));	//묵시적 형변환
Math.ceil((Y-X)/(double) D);	//명시적 형변환

2. Y 이상의 값을 찾기 위해 Math class의 어림 함수 중 올림을 사용하였습니다.
   
   

   Function	Description	Example
   Math.around()	반올림	Math.around(1.1) => 1.0 Math.around(1.9) => 2.0
   Math.ceil()	올림	Math.ceil(1.1) => 2.0
   Math.floor()	내림	Math.floor(1.9) => 1.0