Lv.2 : 점프와 순간 이동

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• 0에서 n까지 이동하는 최소 점프 수를 반환한다.
  • 점프하면 한 칸 앞으로 이동한다.
  • 텔레포트하면 현재 인덱스의 2배 인덱스로 이동하고, 점프 수는 증가하지 않는다.

🔸 문제 풀이 🔸

• 텔레포트는 짝수 인덱스에서만 가능하고, 점프 수가 증가하지 않으므로 무조건 많이 쓰면 좋다.
• 0부터 시작해 n으로 향하면, 쓸 데 없는 경우의 수가 많아지므로 확실히 도착하는 경로를 찾기 위해서 n부터 시작해 0으로 끝나도록 계산한다.
  • 현재 수가 짝수라면 n/2 절반 인덱스로 이동한다. (텔레포트)
  • 현재 인덱스가 홀수라면 -1하고 점프 수 카운트를 +1 한다. (점프)

---

🔸 코드 🔸

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

🔸 코드 해석 🔸

• n이 0이 될 때까지 점프와 텔레포트를 반복한다.
• 점프 수를 카운트해 반환한다.

---

🔸 코드 2 🔸

public class Solution {
    public int solution(int n) {        
        return Integer.bitCount(n);
    }
}

🔸 코드 해석 🔸

• 0부터 n까지 가는 X2연산과 +1 연산은 2진수로 봤을대 '1'이 추가되는 계산이다.
• 따라서 n의 2진수에서 1의 개수를 반환하면 된다.

---

🔸 end 🔸

• 처음엔 단순 BFS풀이 인 줄 알았지만, 효율성 테스트가 있는 문제여서 시간 및 메모리 초과 오류가 잔뜩 났다.
  • 브루트 포스를 쓰기에는 N이 10억까지 가므로 경우의 수가 너무 많아진다.
• DP나 그리디 적인 접근으로 효율적으로 풀어야만 하는데, 그래서 그런지 다른사람 풀이가 유사한 것 뿐이었다.
  • 특이한 건 2진법을 이용한 풀이인데, 간단히 설명하면 X2와 +1연산만 있기 때문에 n을 그냥 2진수로 표현해서 1의 개수를 세면 그게 답이다...
• 2진수 풀이 코드와 채점 결과를 추가했다.
  • 2진수 풀이가 코드는 압도적으로 짧은데, 속도와 메모리는 비슷한 것 같다.