1. 지민이가 가지고 있는 막대의 길이를 모두 더한다. 처음에는 64cm 막대 하나만 가지고 있다. 이때, 합이 X보다 크다면, 아래와 같은 과정을 반복한다.
   • 가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다.
   • 만약, 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같다면, 위에서 자른 막대의 절반 중 하나를 버린다.
2. 이제, 남아있는 모든 막대를 풀로 붙여서 Xcm를 만든다.

풀이1

비트마스킹 분류에 있는 문제라서 비트마스킹으로 풀어보려고 했는데 모르겠어서 일단은 그냥 구현했다.

• 가지고 있던 막대들의 합과 방금 자른 막대의 길이 합이 x보다 작거나 같으면 방금 자른 막대도 이어 붙이고, 개수를 증가시킨다.
  
• 이어 붙인 길이가 x보다 길어지면 사용할 수 없으므로 반으로 자른다.

코드1

package BOJ;

import java.io.*;

public class sol1094 {
    static int x;
    static int stickCount = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        x = Integer.parseInt(br.readLine());

        int exp = 6;
        int sum = 0;
        while (true) {
            int currentStick = 1 << exp;    //  현재 막대의 길이 2^exp
            if (sum + currentStick <= x) {  //  현재 막대를 사용할 수 있다.(이어 붙였을 때 x보다 작거나 같은 경우)
                sum += currentStick;
                stickCount++;
            } else {    // 현재 막대를 사용할 수 없으므로 반으로 자른다
                exp--;
            }

            if (sum == x) { //  이어 붙인 막대 총 길이가 x와 같으면
                break;
            }
        }
        System.out.println(stickCount);
    }
}

풀이2

원래의 의도대로 비트마스킹을 사용한 풀이

결국 x 길이의 막대는 만들어진다.
따라서, x가 어떤 막대 길이의 조합인지를 체크한다.
64cm 길이의 막대에서 시작해서 반으로 잘라가면, 잘린 막대도 결국 2의 제곱수가 된다.

$x = 23 = 10111_2 = 2^1 + 2^2 + 2^3 + 2^4$
즉, 이진수로 나타내었을 때 1의 개수를 카운트 해주면 된다.

1. x의 가장 하위 비트가 1일 경우 해당 길이의 막대가 필요한 것이니 count를 증가시킨다.
2. 가장 하위 비트를 확인했으면, 다음 비트를 확인하기 위해 x를 오른쪽을 시프트한다.

코드2

package BOJ;

import java.io.*;

public class sol1094 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int x = Integer.parseInt(br.readLine());
        int count = 0;

        while (x > 0) {
            if ((x & 1) == 1) count++; // 하위 비트가 1이면 막대기 하나 필요
            x >>= 1; // 오른쪽으로 한 칸 시프트 (다음 비트로 이동)
        }

        System.out.println(count);
    }
}