[그리디] 백준 2885번 초콜릿 식사(Java)

https://www.acmicpc.net/problem/2885

2885번: 초콜릿 식사

📚 문제

정사각형 N개로 이루어진 막대 모양의 초콜릿이 있다. 초콜릿의 크기(정사각형의 개수)는 항상 2의 제곱 형태이다. 즉, 1, 2, 4, 8, 16, ...개의 정사각형으로 이루어져 있다. 

 

막대 초콜릿은 나누기 조금 어렵게 되어 있어서, 항상 가운데로만 쪼개진다. 즉, 정사각형이 D개 있는 막대는 D/2개 막대 두 조각으로 쪼개진다.

 

K개 정사각형을 만들기 위해서, 최소 몇 번 초콜릿을 쪼개야 하는지와 사야하는 가장 작은 초콜릿의 크기를 구하는 프로그램을 작성하시오.  상근이는 초콜릿을 하나만 살 수 있다. 꼭 한 조각이 K개일 필요는 없고, 여러 조각에 있는 정사각형을 합쳤을 때 K개이면 된다.

 

예제 입력 1	예제 입력 2
6	8 2

 

📝 문제 해결

1) 크기 K의 초콜릿을 얻기 위해서는 K와 같거나 큰 2의 제곱 크기의 초콜릿이 필요함

2) 초콜릿의 크기가 K보다 클 경우 반으로 쪼개고 count를 하나씩 더해준다.

3) K가 0보다 작아지면 반복문을 중단한다.

 

💻 코드

import java.util.*;

public class BOJ2885{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int n = 1;
        int count = 0;
        
        while(n<k) n= n*2;
        
        StringBuilder sb= new StringBuilder();
        sb.append(n).append(" ");
        
        while(k>0){
            if(k>=n){
                k-=n;
            }else{
                n/=2;
                count++;
            }
        }
        
        sb.append(count);
        System.out.println(sb);
    }
}