LV2 점프와 순간 이동

---

문제

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

프로그래머스

 

풀이

문제를 처음봤을땐 DP인가 싶었다, 그러나 10억개의 배열을 선언하면 메모리가 터져버린다. 또 다르게는 1칸을 가거나 2배를 가거나 하는 완전탐색을 생각했는데 이건 시간초과를 벗어날 수 없었다.

 

곰곰히 생각해보다가 n에서부터 0을 찾아가면 쉽겠다고 생각이 들었다. 무조건 2배를 해주는게 좋으니 나눌수 있을땐 나누고, 그게 아니라면 -1을 해주고 카운트를 1늘려주면 된다. 이 과정을 n이 0이 될때까지 반복해주면 풀 수 있다.

 

 

코드

import java.util.*;

public class Solution {
    
    public int solution(int n) {
        int cnt = 0;
        
        while(n != 0){
            if(n%2==1){
                n-=1;
                cnt++;
            } 
            n/=2;
        }
        return cnt; 
    }
}

 

후기

 

- 처음에는 n/=2 를 else문에 박았는데 나눌때는 따로 카운트가 늘지않으니 빼도 되더라.

 

- 완전탐색 느낌이 나나 시간초과로 못풀 거 같은 문제가 나온다면 dp나 이진탐색, 또는 역추적을 생각해보자!!