[프로그래머스] 프로그래머스 Level2 점프와 순간 이동 Java

문제

https://programmers.co.kr/learn/courses/30/lessons/12980

코딩테스트 연습 - 점프와 순간 이동

풀이

문제를 처음보자마자 BFS거나 DP라고 생각하고 DP로 풀었는데 전혀 아니었다. 그냥 그리디 비슷한 구현 문제였다. DP로 점화식 세워서 효율성까지 줄여가며 풀었는데 정확성은 만점이었지만 효율성이 0점이 나와서 그냥 단순 구현으로 문제를 풀어 100점을 얻을 수 있었다.

풀이과정을 보자면 예를들어 n = 2인 상태에서 순간 이동을 통해 건전지의 코스트 없이 n = 4까지 이동할 수 있다 또 n = 4는 n = 8로, n = 8은 n = 16으로 계속 거리에 2를 곱해주며 비용 없이 이동할 수 있는데 이 점을 활용하여 n을 계속 2로 나누어주고 이때는 비용이 발생하지 않으므로 2로만 계속 나누어주었고 n이 홀수라 2로 나눌 수 없는 상태일때는 어쩔 수 없이 점프를 해야하므로 건전지의 코스트를 1 늘려주고 1만큼 빼주면 된다. 이 패턴을 n = 0인 상태 즉, 도착할때까지 반복할 수 있도록 while문을 통해 돌려주면 최소의 건전지 코스트를 가진 정답을 구할 수 있다.

코드

import java.util.*;

public class Solution {
    public int solution(int n) {
        int ans = 0;

        while (n != 0) {
            if(n % 2 == 0) {
                n /= 2;
            } else {
                n--;
                ans++;
            }
        }

        return ans;
    }
}

효율성 0점 코드(DP)

import java.util.*;

public class Solution {
    public int solution(int n) {
        int ans = 0;

        int dp[] = new int[n + 1];

        dp[0] = 0;
        dp[1] = 1;

        if(n % 2 == 0) {
            for(int i = 2; i <= n / 2; i++) {
                if(i % 2 == 0) {
                    dp[i] = Math.min(dp[i / 2], dp[i - 1] + 1);
                } else {
                    dp[i] = dp[i - 1] + 1;
                }
            }
            ans = dp[n / 2];
        } else {
            for(int i = 2; i <= n - 1; i++) {
                if(i % 2 == 0) {
                    dp[i] = Math.min(dp[i / 2], dp[i - 1] + 1);
                } else {
                    dp[i] = dp[i - 1] + 1;
                }
            }
            ans = dp[n - 1] + 1;
        }
        return ans;
    }
}