알고리즘/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와 같은 거리에 도착하는 게 기준이므로 이 경우도 나누자.

analysis 중

코드

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;
}

 

문제를 너무 어렵게 바라보지 말자. 쉬운 코드라도 적은 메모리를 사용하고 시간복잡도를 최적화할 수 있다면 그게 맞는 답일 수도 있다.