백준 2885 초콜릿 식사 풀이 (feat. JAVA)

비트마스킹 친해지기 어렵다...

어떻게 써먹어야할지 쓰면서도 헷갈림

더 자주 풀어서 더 친해져야지 뭐 ㅠ

package Record_2025;

/*
[백준]
2885, 초콜릿 식사

[문제파악]
- 학교 근처 편의점에 새 초콜릿이 들어왔다.
- 이 초콜릿은 막대 모양이고, 각 막대는 정사각형 N개로 이루어져 있다.
- 초콜릿의 크기(정사각형의 개수)는 항상 2의 제곱 형태이다.
- 즉, 1, 2, 4, 8, 16, ...개의 정사각형으로 이루어져 있다.
- 상근이는 점심식사로 초콜릿을 먹는다.
- 이때, 적어도 K개 정사각형을 먹어야 남은 수업을 졸지 않고 버틸 수 있다.
- 상근이의 친구 선영이도 초콜릿을 좋아한다.
- 선영이는 초콜릿은 돈을 주고 사기 아깝다고 생각하기 때문에, 상근이가 주는 초콜릿만 먹는다.
- 상근이는 막대 초콜릿를 하나 산 다음에, 정확하게 K개 정사각형이 되도록 초콜릿을 쪼갠다.
- K개는 자신이 먹고 남는 것은 선영이에게 준다.
- 막대 초콜릿은 나누기 조금 어렵게 되어 있어서, 항상 가운데로만 쪼개진다.
- 즉, 정사각형이 D개 있는 막대는 D/2개 막대 두 조각으로 쪼개진다.
- K개 정사각형을 만들기 위해서, 최소 몇 번 초콜릿을 쪼개야 하는지와 사야하는 가장 작은 초콜릿의 크기를 구하는 프로그램을 작성하시오.
- 상근이는 초콜릿을 하나만 살 수 있다.
- 꼭 한 조각이 K개일 필요는 없고, 여러 조각에 있는 정사각형을 합쳤을 때 K개이면 된다.

[입력]
- 첫째 줄에 K가 주어진다. (1 ≤ K ≤ 1,000,000)

[출력]
- 첫째 줄에는 상근이가 구매해야하는 가장 작은 초콜릿의 크기와 최소 몇 번 쪼개야 하는지를 출력한다.

[구현방법]
- 일단 초콜릿 판 하나를 K개 이상이 될때까지 쪼개면 되는 것 아닌가..?
- 그게 아니었음. 일단, K개 이상을 처음부터 가정하고 진행해야 함.
    - 즉, K=6이면, 음! 8개(2^3)가 미니멈이군!!! 한다음, 8개를 픽하면 된다
    - 다만 이게 8개짜리 정사각형 초콜릿으로 구성되어있다지만, 처음엔 단일 1개의 막대 초콜릿일테니? 몇 번 분지르면 6개로 분리해낼 수 있는지를 파악하면 된다
- 재귀를 태우면 문제인게... 흠.. 계속 작은쪽 먼저 부시게 된다
- 이러면 정확한 값을 구할 수 없음
- PQ로 구해야할까?

[보완점]
- 내가 비트를 잘 이해를 못하고 있었나보다
- PQ이런거 필요없고 A to Z 비트로 처리 가능하다
- 마지막 쪼개기 연산이 헷갈렸는데 그냥 계속 /2로 쪼개니까 K에서 계속 빼버리면 된다
- 구해야하는 부분을 줄여가면 됨... 가끔 너무 어렵게 생각하나 싶다
    - 애초에 비트마스킹이 어려움.. 이걸 어떻게 써먹어야 효율적이지? 라는 생각?!
    - 더 자주 풀어서 더 친해져야 할듯하다...
*/

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

public class BOJ_2885_초콜릿식사 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int K = Integer.parseInt(br.readLine());

        // 가장 작은 초콜릿 크기: K보다 크거나 같은 2의 제곱수
        int chocolateSize = 1;
        while (chocolateSize < K) {
            chocolateSize *= 2;
        }

        // 최소 쪼개기 횟수 계산
        int breakCount = 0;
        int piece = chocolateSize;

        // K가 이미 2의 제곱수라면 쪼갤 필요가 없음
        if (K == chocolateSize) {
            System.out.println(chocolateSize + " " + 0);
            return;
        }

        // K를 만들기 위한 최소 쪼개기 횟수 계산
        while (0 < K) {
            piece /= 2;  // 초콜릿을 반으로 쪼갬
            breakCount++;

            if (piece <= K) {  // 현재 조각을 가져갈 수 있으면
                K -= piece;    // 조각을 가져감
            }
        }

        System.out.println(chocolateSize + " " + breakCount);
    }
}