• 문제 출처 : 프로그래머스
• 문제명 : 점프와 순간 이동
• 분류 : Divide and Conquer
• 언어 : Java
• 체감 난이도 : ⭐⭐⭐
• 풀이 시간 : 20min
• Fail Cnt : 0

---

---

1. 문제 접근방식

[문제 조건]
움직이는 방법은 2가지가 있다

• 앞으로 K만큼 이동 -> K만큼 건전지를 사용함
• 위치 a에서 2*a의 위치로 순간이동 -> 건전지 사용량 없음

따라서, 최대한 순간이동을 하되 순간이동으로 움직일 수 없는 거리만 K만큼의 건전지를 사용해 이동한다.

---

---

2. Dynamic Programming

1) 변수 선언

T[i] : 위치 i로 이동할 때, 최소 건전지 사용량

---

2) 예시

(1) n=1일 경우(base-case)
: 앞으로 1만큼 이동한다 (T[1] = 1)

(2) n=2일 경우
: 위치 1에서 순간이동을 사용한다 (T[2] = T[2/2] = 1)

(3) n=3일 경우
: 위치 1에서 순간이동을 해서 위치 2로 이동한다. 그리고 앞으로 1만큼 이동한다. (T[3] = T[3/2] + 1 = 2)

(4) n=4일 경우
: 위치 2에서 순간이동해서 위치 4로 이동한다. (T[4] = T[4/2] = 1)

---

3) 정리

문제 접근 방식

• 이동하려는 위치 n이 짝수인 경우 위치 n/2에서 순간이동을 하면 된다
• 이동하려는 위치 n이 홀수인 경우 위치 n/2에서 순간이동을 해 위치n-1로 이동하고 앞으로 1만큼 이동한다.

즉, T[i] = T[i/2] + (i%2) 이다.

---

4) 코드

    public int solution(int n) {
        int ans = 0;
        //arr[i] : 위치 i로 이동할 때, 최소 건전지 사용량을 저장한다
        int[]arr = new int[n+1];
        
        //base-case
        arr[0] = 0;
        arr[1] = 1;
        //induction step
        for(int i=2; i<=n; i++) {
            arr[i] = arr[(i/2)] + (i % 2);
        }

        ans = arr[n];

        return ans;
    }

---

5) Dynamic Programming으로 코드를 작성하면 안되는 이유

문제 조건에 따르면 입력의 크기는 10억 이하의 자연수이다.
DP방식으로 알고리즘을 작성할 경우, 시간복잡도는 O(n) 이기 때문에 1초를 초과하게 되어 시간초과(Fail)가 발생할 것이다.

---

---

3. Divide and Conquer

1) 분할정복시 시간복잡도

이동하려는 위치가 n일 경우, 위치 n/2에 대한 최소 건전지 사용량을 알아내면 된다.

EX) N=4일경우
T[4] : T[2]를 구하는 함수를 호출해서 리턴
T[2] : T[1]를 구하는 함수를 호출해서 리턴
T[1] : 거리 1이 base-case이므로 1을 리턴

따라서, 시간복잡도는 O(logN)이 된다.

---

2) 코드

    public int divCon(int n) {
    	//종료부
        if(n == 1) { return 1; }
        //재귀함수 호출부(순환부)
        else { return (divCon(n/2) + (n%2)); }
    }

    public int solution(int n) {
        int ans = 0;

	//분할정복해, 문제의 답을 알아낸다
        ans = divCon(n);

        return ans;
    }