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

Graph

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

[풀이]

N이 10억이기 때문에 배열로 체크하는 경우 메모리초과가 나거나 DP를 사용하는 경우 시간초과가 발생한다.

따라서 주어진 N이 홀수인 경우 -1, 짝수인 경우 나누기 2를 해주어 최종적으로 1이 나오도록 만든다.

 

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