[프로그래머스] 점프와 순간이동 - 분할 정복, 재귀

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장.

 

점프와 순간 이동(링크)

접근 방법

주어진 그대로 시작 위치에서 출발하며 규칙을 찾으려고 했다. 순간 이동을 위해서 이동한 거리가 필요하니까 처음 한 칸을 점프하고 순간 이동으로 N까지 최대한 가깝게 이동한 후 점프로 마무리하는 가장 단순한 접근에서 부터 각 위치에서도 점프를 하느냐 마느냐에 따라 결과가 달라지므로 각 위치에서 재귀적으로 점프와 순간 이동을 하려고 생각했지만 너무 많은 경우의 수가 있고 입력이 10억 이하의 자연수인 만큼 모든 위치를 평가해 보기에는 힘들 것 같았다.

풀이

N에 도달하기 위해서 N / 2 위치에서 순간 이동하고 N / 2에 도달하기 위해 N / 4 위치에서 순간 이동 해야 한다.

 

재귀적으로 생각하면, 어떤 목적지에 도달하기 위해 그 절반에 해당하는 위치에 매번 도달해 있어야 하는 것이다. 어떤 목적지가 홀수여서 그 절반의 위치에서 도달할 수 없다면, 한 칸을 점프한 뒤 순간 이동으로 도달할 수 있다. 

 

N에서 부터 절반씩 나누어 가고 홀수일 때는 한 칸을 줄인 뒤 계속 절반씩 나눈다면 0에 도달할 수 있다. 홀수일 때만 즉, 순간 이동으로 도달할 수 없을 때만 한 칸 뛰고 나머지는 항상 절반을 줄이므로 (순간 이동하므로) 최소 횟수로 점프한다.

 

이런 종류의 문제는 시작 위치에서 부터의 이동 방법을 생각하는 것 보다 도착 위치에서 어떻게 되돌아 가는지 생각하면 편하다. (사다리 게임)

시간 복잡도

반복할 때마다 거리를 절반으로 줄이므로 O(logN)의 시간 복잡도를 가진다.

 

#include <iostream>
using namespace std;

int solution(int N) {
    int ans = 0;

    while (N > 0) {
        // N is even number.
        if (N % 2 == 0) {
            N /= 2;
        } else {
        // N is odd number.
            N -= 1;
            ans += 1;
        }
    }
    return ans;
}