[백준] 2885 초콜릿 식사 - Greedy / Java

• 문제 링크

2885번: 초콜릿 식사

 

• 풀이 과정

최소 필요한 정사각형의 개수 k보다 같거나 크며 가장 작은 2의 제곱수를 구하여

이를 초콜릿의 최소 크기로써 n에 대입한다.

 

이어서 초콜릿의 크기가 k보다 클 경우 반으로 쪼개어 cnt++를 수행하고,

초콜릿을 쪼갠 만큼 필요한 k값에서 제외해야 하므로 k -= n을 수행한다.

 

k가 0과 같거나 작을 때까지 이러한 과정을 반복하여,

미리 구한 초콜릿의 최소 크기 n과 쪼갠 횟수 cnt를 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int k = Integer.parseInt(br.readLine());

        int n = 1;
        int cnt = 0;

        while (n < k)
            n *= 2;

        bw.write(n + " ");

        while (k > 0) {
            if (k >= n)
                k -= n;
            else {
                n /= 2;
                cnt++;
            }
        }

        bw.write(String.valueOf(cnt));
        bw.flush();
    }

}