알고리즘/codility사이트
Lesson3 - FrogJmp
SooYoung Kim
2021. 6. 27. 21:15
문제
input : 현재 개구리의 위치 X, 목표 위치 Y, 개구리가 뛰는 fixed 된 거리 D
output : Y보다 더 멀리 혹은 Y 에 도착하기 위해서 뛰어야 하는 jump 수
X, Y, D가 10억 이하이고 X <=Y를 만족한다.
풀이
Lesson3는 time complexity를 다루는 부분이라 해당 문제를 보자마자 이건 dp문제다! 처음에 생각을 했는데 그냥 계산으로 풀리는 문제였다. (문제의 의도에 맞는 풀인지는 모르겠다)
- 거리가 0일 경우, output이 Y 보다 더 멀리 혹은 Y와 같은 거리에 도착하는 게 기준이므로 이 경우도 나누자.

코드
int solution(int X, int Y, int D) {
// write your code in C++14 (g++ 6.2.0)
int distance = Y-X;
//X=Y일 경우
if(distance == 0) return 0;
//X<Y일 경우
if(distance % D == 0) return distance/D;
else return (distance/D) +1;
}
★ 문제를 너무 어렵게 바라보지 말자. 쉬운 코드라도 적은 메모리를 사용하고 시간복잡도를 최적화할 수 있다면 그게 맞는 답일 수도 있다.