Lesson 3(Time Complexity) - 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.

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.

개구리가 목적지까지 가기 위해서 몇번 점프를 해야 되는지 계산하는 문제입니다.

개구리 위치 X, 목표 위치 Y, 개구리 점프 1회당 거리 D가 주어지며 최종적으로 개구리 이동 횟수를 반환해야 됩니다.

 

 

 풀이

 

import java.lang.Math;

class Solution {
    public int solution(int X, int Y, int D) {
        // write your code in Java SE 8
        int res = 0;
        double cal = (double)(Y-X)/D;
        double mod = (double)(Y-X)%D;
        
        if( mod == 0 ) 
            res =  (int) Math.floor(cal);
        else 
            res =  (int) Math.ceil(cal);

        return res;
    }
}

아주 쉬운 계산 문제입니다.

1차 방적식을 사용하여 풀면 간단합니다.

 

X : 현재 위치
Y : 목표 거리
D : 한번 이동시 거리
N : 회수

 

Y <= ND + X

N >= (Y-X)/D

 

* 단 주의점은 N이 정수로 나누어지지 않을때는 올림을 해야 되며 나누어떨어질때는 해당 값을 반환해야 합니다.

올림(ceil), 내림(floor) 함수 사용을 위해 java.lang.Math를 사용하였습니다.

 

 결과

 

URL : app.codility.com/demo/results/trainingUCW8BE-65K/

 

제출 결과 1

제출 결과2

제출 결과입니다. 정확도도 100점 받았고 문제풀이를 수식으로 풀어 시간 복잡도도 1로 나왔네요.