[프로그래머스] 점프와 순간이동 (DP_JAVA)

문제를 보고 dp인줄은 생각하고 있었는데,

풀이과정이 안떠오르다가

노트에 끄적이니까 문득 떠올라서 푼 문제!

 

 

---

문제

 

https://school.programmers.co.kr/learn/courses/30/lessons/12980

프로그래머스

 

 

 

---

설계

 

 

알고리즘 설계 [접근 방법] : DP 사용

이 경우는 dp로 풀었다.

처음에 풀이 방법은 모든 testcase를 맞추었지만, 시간초과와 메모리초과가 발생했다.

그래서 시간 단축과 메모리 단축을 계속 생각했고 2번째 풀이를 생각했다.

 

첫 번째풀이 : 메모리초과

1. 배열을 크키 n+1로 지정한 한다.

2. 인덱스가 짝수이면 인덱스/2한 값을 그대로 부여하고,

3. 인덱스가 홀수이면 인덱스/2한 값 +1을 배열 값에 부여한다.

4. 배열[n]값을 반환한다

: n 크기의 배열을 만들고 1부터 n까지 반복문을 실행하니 시간초과와 메모리 초과가 발생했다.

 

 

두 번째 풀이 : DP

1. n값이 2보다 작거나 같을 때까지 반복문을 실행한다.

2. n%2한 값이 0이라면 넘어가고,

3. n%2한 값이 1이라면 ans를 +1해준다.

4. ans 값을 반환한다.

: n/2를 하며 반복문을 진행하니 횟수가 크게 줄었고, 배열을 사용하지 않았다.

 

 

---

코드

 

[첫 번째 풀이]

import java.util.*;

public class Solution {
    public int solution(int n) {
        
        /*
        answer[1]은 무조건 점프를 해야하므로 1이다.
        answer[1]에서 1만큼 순간이동하면 되므로 answer[2]의 값도 1이 된다.
        */
        
        if(2<n) {
            int[] answer = new int[n+1];
        
            answer[1]=1;
            answer[2]=1;

            //3부터 n까지 반복문 실행
            for(int i=3; i<answer.length; i++){
                if(i%2==1) answer[i]=answer[(i/2)]+1;
                else answer[i]=answer[(i/2)];
            }

            int ans = answer[n];
            return ans;
        }
        
        //만약 n이 1과 2라면, 1반환
        return 1;
    }
}

 

 

[두번째 풀이]

import java.util.*;

public class Solution {
    public int solution(int n) {
        
        int ans=1;
        while(2<=n){
            if(n%2==1) ans+=1;
            n/=2;
        }

        return ans;
    }
}

 

 

(❁´◡`❁)

끝!