[프로그래머스/Lv.2] 점프와 순간 이동 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

(틀림 : DP)

틀림 : DP 활용한 풀이

import java.util.*;
import java.io.*;
 
public class Solution {
    public long solution(int n) {
        int ans = 0;
    
        long[] dp = new long[n + 1];
        dp[1] = dp[2] = 1;
        
        if(n <= 2) {
            return dp[n];
        }
        
        for(int i = 3 ; i <= n ; i++) {
            dp[i] = (i % 2 == 0) ? dp[i / 2] : (dp[i-1] + 1) ;
        }
 
        return dp[n];
    }
}

 

- 정답

import java.util.*;
import java.io.*;
 
public class Solution {
    public int solution(int n) {
        int ans = 0;
    
        while(n > 0) {
            if(n % 2 == 1) {
                ans++;
            }
            
            n /= 2;
        }
        
        return ans;
    }
}

✅ 해결 아이디어
✔ 재귀 (Top-Down)
- n/2가 홀수인 경우, ans에 1을 더함
- 위 과정을, n이 0보다 클 때까지만 반복

 

💥 유의사항

• 숫자 N, 1 이상 10억 이하의 자연수

 

 

---

🔺 다른 풀이들

[프로그래머스 - Java] 점프와 순간 이동

 

---

💬 느낀 점

DP로 풀려다가 장렬히 실패..

담엔 더 빨리 풀겠다

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[Java] 프로그래머스 - 점프와 순간 이동 (Level 2)