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)

마무리

문제는 길지만 사실 무척 쉽고 간단한 문제였다!

Reference & Learn More

MDN Math.ceil()

Tags
Comments