점프와 순간 이동

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

프로그래머스

 

K = 1 인 케이스부터 소모되는 전력(ans)을 구하고,

 

K 를 ans까지 늘여가며 소모되는 전력을 구한 뒤 최소값을 찾으면 될거같은데

 

import java.util.*;

public class Solution {
    public int solution(int n) {

        int ans = n;
        
        for (int i = 1; i <= ans; i += 2) {
            int power = consume(n, i, ans);
            ans = Math.min(power, ans);
        }

        return ans;
    }
    
    int consume(int n, int K, int min) {
        int power = 0;
        while (n > 0) {
            if (n % 2 == 0) {
                n /= 2;
            } else {
                n -= K;
                power += K;
            }
            if (power > min) break;
        }
        return power;
    }
    
}

 

결국 K = 1이 무조건 최소 전력을 소모하는 듯하다.

 

import java.util.*;

public class Solution {
    public int solution(int n) {
        return consume(n, i);
    }
    
    int consume(int n, int K) {
        int power = 0;
        while (n > 0) {
            if (n % 2 == 0) {
                n /= 2;
            } else {
                n -= K;
                power += K;
            }
        }
        return power;
    }

}

 

그럼 그냥 2진수로도 풀 수 있다..

import java.util.*;

public class Solution {
    public int solution(int n) {
        return useBinary(n);
    }
    
    int useBinary(int n) {
        String bin = Integer.toString(n, 2);
        int cnt = 0;
        for (int i = 0; i < bin.length(); i++) {
            if (bin.charAt(i) == '1') cnt++;
        }
        return cnt;
    }
}

 

처음엔 bin을 replaceAll로 0을 제거한 뒤 총 글자 수를 반환했는데,

 

시간 초과가 뜨더라..