FrogJmp
/Codility문제 해석
요약
정수 X, Y, D가 주어진다. X ≤ Y 이고, X, Y, D는 1~1,000,000,000의 정수.
X는 현 위치이고 Y는 종착점까지 거리, D는 점프 거리이다. X에서 D만큼씩 몇 번 점프하면 Y에 도착하는지 구하여라.
전문
🇰🇷 번역
작은 개구리는 다른 쪽의 길로 가길 원한다. 개구리는 현재 위치 X에 위치하고 있고, Y보다 더 크거나 같은 위치에 가길 원한다. 작은 개구리는 항상 고정된 거리인 D만큼 점프합니다.
작은 개구리가 목표에 도달하기위해 수향해야할 최소 점프 수를 카운트해라.
함수를 작성하시오:
function solution(X, Y, 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.
🇺🇸 원문
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:
function solution(X, Y, 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에다 D를 몇 번(#) 더하면 Y보다 커지는 가.
를 식으로 세우면 아래와 같다.
Y ≤ X + @D
@를 구하는 것이 목적이므로 이항하면,
Y - X ≤ #D
(Y - X) / D ≤ #
조건을 만족하는 가장 작은 정수를 구하면 된다.(반올림!)
코드 구현
function solution (X, Y, D) {
if (X === Y) return 0;
return Math.ceil((Y - X) / D);
};결과 분석
Task Score: 100%
Correctness: 100%
Performance: 100%
시간 복잡도는 O(1)이고, 따로 필요한 공간 없이 바로 값만 리턴하는 방법으로 계속 일정하므로 공간복잡도는 O(1)
마무리
문제는 길지만 사실 무척 쉽고 간단한 문제였다!