[프로그래머스/JAVA] 점프와 순간 이동

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

프로그래머스

📌 문제 요약 

아이언 슈트는 두 가지 이동 방식이 있습니다:

1. 순간이동: 현재 위치에서 x2로 이동 (건전지 소모 X)
2. 점프: 앞으로 K칸 이동 (건전지 소모 K)

목표 거리 N에 도달하기 위해 건전지 사용량을 최소화하는 것이 목표입니다.

---

 

[ 오답 노트 ]
❌ 기존 오답 코드

import java.util.*;

public class Solution {
    public int solution(int n) {
        int ans = 0; // 건전지 사용량 
        int trs = 0; // 현재위치 
        
        // 먼저 1칸 점프 -> 사용량1
        trs += 1; ans += 1;
        
        while(trs < n) { // 현재 위치가 5가 되면 종료 
            // 짝수, 홀수일 경우로 나누기
            if(trs % 2 != 0) { // 홀수라면 
                trs = trs * 2;
            }else{ // 짝수라면
                trs += 1; ans += 1;
            }

            if(trs == n) {
                break;
            }
            
        }

        return ans;
    }
}

 

📌 기존 코드의 문제점

기존 코드의 논리는 "현재 위치가 짝수라면 순간이동, 홀수라면 1칸 점프"하는 식으로 구현하려 한 것으로 보입니다. 하지만 이 논리에는 문제가 있습니다. 2배 순간이동은 어디서든 사용할 수 있는 것이 아니라, "이동이 현재 위치 x 2일 때"만 가능합니다.

1. 홀수/짝수 구분이 잘못됨: 이동 거리 trs를 기준으로 체크하면서 짝수/홀수 구분이 어색합니다.
2. 반복 로직 오작동: 현재 위치 trs를 올바르게 업데이트하지 않고, 순서를 잘못 구현하여 무한 반복하거나 잘못된 결과가 나올 수 있습니다.

---

 [ 정답 코드 & 올바른 풀이 ]

📌 올바른 풀이

1. 뒤에서부터 거꾸로 생각하면 됩니다. 즉, 목표 거리 N에서 시작해서 0으로 돌아가는 과정을 반대로 시뮬레이션합니다.
2. 홀수일 때만 점프를 해야 하므로, N을 계속 나누면서 홀수일 때마다 점프 횟수를 기록합니다.
3. 짝수일 경우 순간이동만 하면 됩니다. 순간이동은 배터리를 소모하지 않기 때문입니다.

---

 

📌 정답 코드

import java.util.*;

public class Solution {
    public int solution(int n) {
        int ans = 0; // 건전지 사용량 
        
// n = 5일때,
// 0 -> 1칸 점프 (사용량1) -> 순간이동 1*2 = 2로 이동
//-> 순간이동해서 2*2 = 4로이동 -> 1칸 점프(사용량1) : 총 사용량 2

// n = 6일때, 
// 0 -> 1칸 점프 (사용량1) -> 순간이동 1*2 = 2로 이동 
//-> 1칸 점프(사용량1) 위치3 -> 순간이동 3*2 = 6 : 총 사용량 2
        
// n = 5000일때,
// 0 -> 1칸 점프 (사용량1) -> 순간이동 1*2 = 2로 이동 
//-> 순간이동 2*2 = 2로 이동 .... -> 
        
        // 거꾸로 생각하기 (n부터 0으로, 즉 따로 거리 변수 만들 필요 없이 n을 줄여가며 사용!)
        while(n > 0) {
            if(n % 2 == 0) { // 짝수라면
                n /= 2; // 순간이동
            }else{ // 홀수라면 
                n -= 1;// 점프
                ans++; // 건전지 사용량 +1 
            }
            
        }

        return ans;
    }
}