12980. 점프와 순간 이동

2026-04-02

프로그래머스 12980번 풀이

문제

풀이

아이디어

문제에서 너무 익숙한 DP의 맛이 나서 그냥 아무 생각 없이 Bottom-Up으로 풀었다. (사람은 생각을 하며 살아야 한다…) 시간초과가 나서 왜인가 봤더니 N이 최대 10억이어서 O(N) 풀이가 불가능했다.

그래서 Top-Down으로 풀이 방향을 바꿨다. 목적지 N에서 거꾸로 거슬러 올라가면 두 가지 경우로 나뉜다.

짝수: N/2 위치에서 순간이동해서 왔을 것 → 배터리 소모 없음
홀수: N-1 위치에서 1칸 점프해서 왔을 것 → 배터리 1 소모

이 규칙을 재귀로 적용하면 N을 계속 절반으로 줄여가며 홀수일 때만 카운트하면 된다.

메모이제이션은 DP답게 Array를 이용했다.

const usage = new Array(n + 1).fill(0);

그런데!!! 자꾸 시간초과가 발생하는것이다… 대체 O(log N)보다 어떻게 줄여야 하는 것이냐 하며 머리를 싸맸는데 알고보니 메모리 초과 문제였다. N이 최대 10억이기 때문에… 메모이제이션 배열에 드는 O(N)공간 역시 너무 컸던 것이다.

사실 Top-Down이기 때문에 모든 값을 메모할 필요는 없다. 따라서 배열 대신 Map을 이용해서 필요한 값만 메모하도록 수정했다. 그러자 시간초과도 해결되었다.

코드

function solution(n) {
  const usage = new Map();
  usage.set(0, 0);
  usage.set(1, 1); // 1칸 점프

  function go(i) {
    if (usage.get(i) !== undefined) return usage.get(i);
    if (i % 2 === 0) usage.set(i, go(i / 2));
    else usage.set(i, go(i - 1) + 1);
    return usage.get(i);
  }

  return go(n);
}

시간 / 공간 복잡도

시간 복잡도: O(log N) - N을 절반씩 나누며 재귀 호출하므로
공간 복잡도: O(log N) - Map에 저장되는 항목 수가 재귀 깊이에 비례

풀이 2

아이디어

풀이 1의 규칙을 다시 보면:

짝수 → N/2로 이동 (비용 0)
홀수 → N-1로 이동 (비용 1)

이 과정은 N을 오른쪽으로 1비트씩 시프트하는 것과 동일하다. 홀수일 때, 즉 최하위 비트가 1일 때만 비용이 발생한다. 결국 N의 이진수 표현에서 1의 개수가 정답이다.

예: N = 11 (1011₂) → 1이 3개 → 배터리 3

코드

function solution(n) {
  return n.toString(2).split('').filter((b) => b === '1').length;
}

시간 / 공간 복잡도

시간 복잡도: O(log N) - 이진수 변환에 O(log N)
공간 복잡도: O(log N) - 이진수 문자열 길이

여담

풀이 2는 “2배 텔레포트 계열” 문제를 풀 때 자주 나오는 패턴이라고 한다. 확실히 메모이제이션하는 것 보다는 간단하고 효율적인 방식이기 때문에 잘 기억해두는게 좋겠다.