알고리즘 - 분할정복(점프와 순간 이동)

aquarius1997·2020년 5월 29일
0

Algorithm

목록 보기
9/9
  • 문제 출처 : 프로그래머스
  • 문제명 : 점프와 순간 이동
  • 분류 : 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;
    }
profile
안녕하세요😀😀

0개의 댓글