본 글은 글쓴이의 개인적인 생각이 담겨있을 수 있습니다.

프로그래머스 [Programmers]
LEVEL - 2
점프와 순간 이동
https://programmers.co.kr/learn/courses/30/lessons/12980

🍔 문제 파악

문제

도착지까지의 거리 n이 존재할 때, 슈트를 입고 도착지까지 가고자 한다.
가는 방법은 점프와 순간 이동이 존재하는데,
점프를 하면 +1 증가하고 연료가 1 사용된다.
순간 이동을 하면 이동 거리가 (현재까지의 이동 거리) * 2가 되고 연료는 닳지 않는다.
도착지까지 가장 적은 연료로 갈 때, 소비한 연료의 양을 구하라.

주의사항

• 거리 n은 1이상 10억 이하의 자연수이다.

🍟 해결

이번 문제의 핵심은 문제를 해결하는 방법 자체이다.
나는 처음 이 문제를 만났을 때, "그리디로 푸는 문제인가?" 라는 생각을 했었다.
하지만 지금까지 온 거리가 0일 때 최선의 선택은 무엇인가? +1이라고 생각할 수 있다.
그러면 1에서는? 이런식으로 풀게 되면 각각의 상황에서 최선의 선택을 하더라도
최적의 값이 나오지 않을 수도 있다. 당장에 n이 1023만 봐도 그렇다.

DP로도 생각했지만 도저히 DP로 생각할 수 있는 문제 형식이 아니었다.
하지만 프로그래머스에 '입출력 예'로 나와 있는 n이 5000일 경우를 생각해보았다.

n이 5000일 경우에 단 5번 만의 점프로 갈 수 있다고 하는데,
도저히 내 머리로는 이 5000이라는 숫자를 만들어낼 수 없었다.
결국 머리를 싸맨 결과 0에서부터 시작하는 것이 아니라
5000에서부터 시작해서 /2 와 -1을 하는 것이었다.
/2를 하는 것은 연료가 들지 않으므로 패스하고,
-1을 하는 것은 연료가 드므로 count의 값을 1 증가시킨다.

다음은 점프와 순간 이동 문제의 해결 코드이다.

public class Solution {
    public int solution(int n) {
        int count = 0;
        while(true) {
            if(n == 0) {
                return count;
            } else if(n % 2 == 0) {
                n /= 2;
            } else {
                n--;
                count++;
            }
        }
    }
}

🌭 느낀 점

역시 알고리즘 문제는 많아도 1시간 동안 고민하면
내가 풀 수 있을만한 문제는 푸는 방법이 생각이 난다는 것을 알게 되었다.
이번에는 방과 후 알고리즘 시간에 프로그래머스를 풀고 있었는데
0부터가 아닌 5000부터 생각하는 것을 떠올린 뒤
내가 생각했다는 게 믿기지가 않았다.