BOJ - 2885 초콜릿 식사

Problem

---

Solve

해당 문제는 가장 작은 초콜릿과 그 초콜릿으로 최소 몇번 쪼개야하는지를 구하는 문제이다.

가장 작은 초콜릿을 구하는 방법은 초콜릿의 크기에 힌트가 있다.
초콜릿의 크기는 2의 제곱형태(1,2,4,8,16...)으로 이루어져 있고 크기의 절반으로 나눌수 있기 때문에 각 초콜릿의 크기는 이전 초콜릿 크기를 나눈다면 어떻게든 만들수 있다.

즉, 해당 초콜릿의 크기는 이전 초콜릿 크기 +1 부터 해당 초콜릿의 크기까지의 초콜릿을 구할수 있다.

예를 들어 크기가 4인 초콜릿은 크기가 1부터 4까지의 초콜릿을 구할 수 있다. 크기가 2인 초콜릿은 크기가 1부터 2까지의 초콜릿을 구할 수 있다.
그러므로 구하려는 초콜릿의 크기가 3일때 2보다는 크기 때문에 3의 크기의 초콜릿을 구할 수 있는 최소의 초콜릿은 크기가 4인 초콜릿이 된다.

최소 초콜릿 크기를 구했다면 최소 몇번 쪼개야 K만큼의 초콜릿을 구할 수 있는지를 알아야한다.

최소 초콜릿 크기를 size라고 했을 때,

• K < size라면 해당 초콜릿 크기는 K개의 초콜릿을 구할 수 없기 때문에 초콜릿을 반으로 나눠야한다.
• K > size라면 해당 초콜릿 크기는 K개의 초콜릿의 부분이 될 수 있기 때문에 K -= size를 함으로써 구해야하는 초콜릿의 개수를 갱신해준다.
• K == size라면 해당 초콜릿 크기는 K개의 초콜릿의 부분이 될 수 있기 때문에 K > size와 동일하게 K를 갱신해준다.

즉, K < size라면 초콜릿을 반으로 나누고, K >= size라면 구해야하는 초콜릿 크기를 갱신해야한다.

---

Code

public class 초콜릿식사 {

	static int minSize;
	static int divisionCount;

	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 size = 0;
		int idx = 0;
        //최소 초콜릿 크기
		while (size < K) {
			size = (int)Math.pow(2, idx++);
		}

		minSize = size;
		divisionCount = 0;

		//구해야하는 초콜릿 크기가 0이 될때까지 반복
		while(K>0){
        	//구해야하는 초콜릿 크기 갱신
			if(K>=size){
				K -= size;
			}
            //해당 크기로는 K개를 구할 수 없기 때문에 초콜릿 반띵
            else{
				size /= 2;
				divisionCount++;
			}
		}
		StringBuilder sb = new StringBuilder();
		sb.append(minSize);
		sb.append(' ');
		sb.append(divisionCount);
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}

---

Result

---

Reference

https://seeminglyjs.tistory.com/77