[Codility] FrogJmp

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.

 

일반적으로 생각해보면, X에서 D*Y 를 for문으로 돌리면서 Y>=X 인 최초의 값을 Return하면 될것 같이 느껴진다.

하지만 이 방식은 O(N) 이다.

 

조금만 더 생각해보면 이 최솟값은 (Y-X) / D 을 올림한 값이라는 사실을 알 수 있다. 정수 N의 올림은 N이기 때문에 Y>= X 의 조건을 만족한다.

이 식을 이용한다면 O(1) 의 시간 복잡도로 문제를 해결할 수 있다. 

 

하지만 처음 코드를 짤때 (Y-X) / D 를 한번에 계산했을때 부동소수점 표현으로 인한 계산 문제가 있어서

두 단계로 나누어서 표현했다.

 

다른 실수 문제를 풀 때 또한, 실수 계산의 경우 계산상의 문제가 있을 수 있어 BigDecimal로 바꿔 표현하는 방법을 알아두는 편이 좋다.

import java.lang.Math;

class Solution {
    public int solution(int X, int Y, int D) {
        // write your code in Java SE 8
        
        double result = 0;
        
        result = (Y-X);
        result /= D;
        result = Math.ceil(result);
        
        return (int)result;
    }
}