프로그래머스

프로그래머스 점프와 순간 이동 풀이: 홀수 위치만 점프하는 그리디

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

  • 문제: 점프와 순간 이동
  • 출처: 프로그래머스, Summer/Winter Coding(~2018)
  • 자체 판단 난이도: Level 2

목적지에서 현재 위치를 거꾸로 생각하면 짝수 위치는 무료 순간 이동으로 절반이 되고, 홀수 위치에서만 배터리를 사용하는 규칙을 바로 얻을 수 있다. 반복문과 나머지 연산을 이용하는 구현은 간단하지만, 이동 방향을 뒤집어 그리디 기준을 찾아야 하므로 Level 2로 판단한다.

1. 문제 요약

현재 위치에서 다음 두 가지 이동을 할 수 있다.

  • 앞으로 K칸 점프: 배터리를 K만큼 사용한다.
  • 현재 위치의 두 배 위치로 순간 이동: 배터리를 사용하지 않는다.

위치 0에서 시작해 N만큼 떨어진 목적지에 도착할 때 필요한 최소 배터리 사용량을 반환한다. 점프의 K는 이동마다 선택할 수 있는 양의 정수이고, 입력으로 주어지는 값은 N뿐이다.

조건은 다음과 같다.

  • N은 1 이상 1,000,000,000 이하의 자연수다.
  • 순간 이동은 현재 위치를 두 배로 만든다.
  • 점프는 원하는 양만큼 할 수 있지만, 점프한 칸 수만큼 배터리를 사용한다.
  • 반환값은 목적지에 도착하기 위한 최소 배터리 사용량이다.

예를 들어 N = 5일 때 0 -> 1로 1칸 점프한 뒤 1 -> 2 -> 4로 순간 이동하고, 마지막에 1칸 점프하면 배터리 2만 사용한다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

그리디 선택 기준

현재 위치를 목적지 N에서 시작해 0 방향으로 거꾸로 줄여 본다.

  • 현재 위치가 짝수이면, 원래는 바로 앞 위치의 두 배에서 순간 이동해 도착할 수 있다. 따라서 n을 n // 2로 줄이고 배터리를 사용하지 않는다.
  • 현재 위치가 홀수이면, 순간 이동의 결과는 항상 짝수이므로 순간 이동만으로는 현재 위치에 도착할 수 없다. 이때는 마지막 이동으로 점프가 필요하므로 배터리 사용량을 1 늘리고 n을 1 줄인다.

홀수 위치에서 2칸 이상 점프하는 것보다 1칸만 점프하는 것이 항상 유리하다. n이 홀수면 n - 1은 짝수이므로, 먼저 1칸 점프한 뒤 남은 거리를 순간 이동으로 처리할 수 있다.

역방향으로 보면 홀수 위치만 배터리가 드는 이유

순간 이동은 위치를 두 배로 만들기 때문에 역방향에서는 짝수 위치를 정확히 절반으로 줄이는 무료 연산이 된다. 반대로 홀수 위치는 어떤 정수의 두 배도 아니므로 역방향에서 반드시 점프를 한 번 거쳐야 한다.

예를 들어 N = 13의 역방향 처리는 다음과 같다.

13 (홀수): 점프 1회, 배터리 1 -> 12
12 (짝수): 순간 이동 역산 -> 6
6  (짝수): 순간 이동 역산 -> 3
3  (홀수): 점프 1회, 배터리 2 -> 2
2  (짝수): 순간 이동 역산 -> 1
1  (홀수): 점프 1회, 배터리 3 -> 0

각 홀수 위치에서 점프 1회를 세고, 짝수 위치에서는 계속 2로 나누면 된다. 이 값은 N을 이진수로 표현했을 때 1의 개수와도 같다. 홀수 판정과 2로 나누기는 이진수의 마지막 비트를 제거하는 과정이기 때문이다.

그리디 선택이 최적인 이유

현재 역방향 위치가 짝수 n이라고 하자. n에 도착하는 방법 중 n // 2에서 순간 이동하는 방법은 비용이 0이다. 같은 단계에서 점프로 n에 도착하면 최소 1 이상의 배터리를 사용하므로 무료 순간 이동보다 좋을 수 없다.

현재 위치가 홀수라면 순간 이동의 도착 위치는 항상 짝수이므로 마지막 이동은 점프여야 한다. 이때 2칸 이상 점프하는 경로가 있다면 마지막 점프 중 1칸만 남기고 나머지 거리를 앞선 순간 이동 경로로 처리할 수 있다. 따라서 최소 비용 경로에는 홀수 위치마다 1칸 점프만 남겨도 충분하다.

이 두 가지 경우가 모든 위치에서 선택을 결정하므로, 홀수 위치의 개수를 세는 방식으로 최소 배터리 사용량을 얻을 수 있다.

오답 접근과 반례

항상 1칸씩 점프하면 목적지에는 도착하지만 배터리를 너무 많이 사용한다.

N = 6
항상 1칸 점프: 배터리 6
최적 이동: 0 -> 1 점프, 1 -> 2 순간 이동, 2 -> 3 점프, 3 -> 6 순간 이동
최소 배터리: 2

반대로 항상 가장 큰 거리만 점프하려 하면 N이 짝수일 때 무료 순간 이동을 놓치게 된다. N = 6에서 6칸 점프를 하면 배터리 6이 필요하지만, 홀수 위치에서만 점프하면 배터리 2로 도착할 수 있다.

시간·공간 복잡도

매 단계에서 n이 홀수이면 1을 빼고, 짝수이면 2로 나눈다. 짝수일 때마다 값이 절반으로 줄어들므로 반복 횟수는 O(log N)이다. 변수 몇 개만 사용하므로 공간 복잡도는 O(1)이다.

3. 문제 해결 코드 (Python)

n을 목적지에서 0까지 거꾸로 줄이며 홀수 위치에서만 battery를 증가시킨다. n이 짝수일 때는 무료 순간 이동을 역산해 2로 나눈다.

def solution(n):
    battery = 0

    while n > 0:
        if n % 2 == 1:
            battery += 1
            n -= 1
        else:
            n //= 2

    return battery

n이 홀수인 경우 먼저 1을 빼야 다음 반복에서 짝수 여부를 다시 판단할 수 있다. 짝수인 n은 n // 2에서 순간 이동한 결과로 볼 수 있으므로 배터리를 증가시키지 않는다. n이 0이 되면 출발점에 도달한 것이므로 battery를 반환한다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 홀짝 역산과 거듭제곱 경계를 확인할 수 있다.

assert solution(5) == 2
assert solution(8) == 1
assert solution(1) == 1

4. 공식 예제와 추가 검증

작성한 solution 함수를 Python으로 실행해 공식 예제와 경계 조건을 확인했다.

공식 예제

입력 기대 출력 확인 결과
N = 5 2 통과
N = 6 2 통과
N = 5000 5 통과

추가 검증 1: 최소 입력

입력: N = 1
기대 출력: 1
확인 결과: 통과
검증 목적: 출발점에서 1칸 점프하는 최소 입력을 확인

추가 검증 2: 2의 거듭제곱

입력: N = 8
기대 출력: 1
확인 결과: 통과
검증 목적: 한 번 1칸 점프한 뒤 순간 이동만으로 도착하는 경우를 확인

추가 검증 3: 홀수와 짝수 역산이 섞인 경우

입력: N = 13
기대 출력: 3
확인 결과: 통과
검증 목적: 홀수 위치에서 점프를 세고 짝수 위치를 나누는 과정을 확인

추가 검증 4: 제한에 가까운 입력

입력: N = 1,000,000,000
기대 출력: 13
확인 결과: 통과
검증 목적: 큰 N에서도 반복 횟수가 작고 이진수의 1 개수를 올바르게 세는지 확인

5. 다른 풀이 방식 검색 및 비교

정방향으로 동적 계획법을 적용하면 각 위치까지의 최소 배터리 사용량을 저장할 수 있지만, N이 최대 10억이므로 모든 위치를 배열로 만드는 방식은 비효율적이다. 역방향 그리디는 짝수 위치를 즉시 절반으로 줄이고 홀수 위치만 세므로 O(log N) 시간과 O(1) 공간에 해결한다.

또 다른 표현으로는 N의 이진수에서 1 비트의 개수를 세는 방법이 있다. 이 문제의 이동 규칙에서는 각 1 비트가 한 번의 1칸 점프에 대응하고, 0 비트는 순간 이동으로 제거되는 과정과 같다.

마무리

점프와 순간 이동은 앞으로 이동하는 문제처럼 보이지만, 목적지에서 출발점으로 거꾸로 보면 규칙이 단순해진다. 짝수 위치는 무료 순간 이동으로 절반이 되고, 홀수 위치에서만 1칸 점프 비용을 추가하면 된다. 따라서 N을 반복해서 홀수에서는 1을 빼고 짝수에서는 2로 나누면 최소 배터리 사용량을 O(log N) 시간에 구할 수 있다.

#그리디#프로그래머스#난이도 2