[백준] 1094번 - 막대기 [Java][C++]

문제 링크

---

1. 문제 풀이

길이 $64$ 인 막대기를 가지고 길이 $X$ 인 막대기를 만들어야 하는데 현재 가지고 있는 막대기의 길이의 합이 $X$ 보다 크면 가지고 있는 막대기 중 길이가 가장 짧은 것을 절반으로 자르고, 자른 막대기 중 하나를 버리고 남은 막대기의 길이의 합이 $X$ 보다 크거나 같다면 자른 막대기 중 하나를 버리는 과정을 반복한다. 이때 길이 $X$ 인 막대기를 만들 수 있을 때 막대기의 수를 구해야 한다.

예제 입력 1을 예로 들면 길이 $64$ 인 막대기로 길이 $23$ 인 막대기를 만들어야 하는데 길이 $64$ 인 막대기를 절반으로 잘라 길이 $32$ 인 막대기 두 개로 만든다. 이때 자른 막대기 중 하나를 버리고 남아 있는 막대기의 길이의 합인 $32$ 가 $23$ 보다 크므로 $32$ 인 막대기는 버린다. 현재 길이 $32$ 인 막대기 하나만 가지고 있다.

이제 길이 $32$ 인 막대기가 $23$ 보다 크므로 다시 막대기를 절반으로 잘라 길이 $16$ 인 막대기 두 개로 만든다. 이때 자른 막대기 중 하나를 버리고 남아 있는 막대기의 길이의 합인 $16$ 이 $23$ 보다 작으므로 버리지 않는다. 현재 길이 $16$ 인 막대기 두 개를 가지고 있다.

이제 길이 $16$ 인 막대기 하나를 절반으로 잘라 길이 $8$ 인 막대기 두 개로 만든다. 이때 자른 막대기 중 하나를 버리고 남아 있는 막대기의 길이의 합인 $16 + 8 = 24$ 가 $23$ 보다 크므로 길이 $8$ 인 막대기 하나를 버린다. 현재 길이 $16$, $8$ 인 막대기를 가지고 있다.

이제 가지고 있는 막대기 중 길이가 가장 짧은 길이 $8$ 의 막대기를 절반으로 잘라 길이 $4$ 인 막대기 두 개로 만든다. 이때 자른 막대기 중 하나를 버리고 남아 있는 막대기의 길이의 합인 $16 + 4 = 20$ 이 $23$ 보다 작으므로 버리지 않는다. 현재 길이 $16$ 인 막대기 하나, 길이 $4$ 인 막대기 두 개를 가지고 있다.

이제 가지고 있는 막대기 중 길이가 가장 짧은 길이 $4$ 의 막대기를 절반으로 잘라 길이 $2$ 인 막대기 두 개로 만든다. 이때 자른 막대기 중 하나를 버리고 남아 있는 막대기의 길이의 합인 $16 + 4 + 2 = 22$ 가 $23$ 보다 작으므로 버리지 않는다. 현재 길이 $16$ 인 막대기 하나, 길이 $4$ 인 막대기 하나, 길이 $2$ 인 막대기 두 개를 가지고 있다.

이제 가지고 있는 막대기 중 길이가 가장 짧은 길이 $2$ 의 막대기를 절반으로 잘라 길이 $1$ 의 막대기 두 개로 만든다. 이때 자른 막대기 중 하나를 버리고 남아 있는 막대기의 길이의 합인 $16 + 4 + 2 + 1 = 23$ 이 $23$ 과 일치하므로 $4$ 개의 막대기로 길이 $23$ 의 막대기를 만들 수 있다.

결과를 보면 알 수 있듯이 $X$ 를 2의 제곱수들의 합으로 표현했을 때 수의 개수와 일치하는 것을 알 수 있다. 이는 $X$ 를 2로 나눈 나머지를 활용한 방식과 비트마스킹을 활용한 방식 등 다양하게 구할 수 있다.

---

2. 코드

1. 수학 [Java]

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int X = Integer.parseInt(br.readLine());
        int cnt = 0;

        while (X > 0) {
            if (X % 2 == 1) cnt++;
            X /= 2;
        }

        System.out.println(cnt);
    }
}

2. 비트마스킹 [Java]

Integer.bitCount 메서드로 $1$ 인 비트만 바로 셀 수 있다. $X$ 를 2의 제곱수들의 합으로 표현했을 때 수의 개수는 2진수로 나타냈을 때 $1$ 인 비트의 개수와 동일하다.

import java.io.*;

public class Main2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        System.out.println(Integer.bitCount(X));
    }
}

3. 수학 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int x;
    cin >> x;

    int cnt = 0;
    while (x > 0) {
        if (x % 2 == 1) cnt++;
        x /= 2;
    }

    cout << cnt;
}

4. 비트마스킹 [C++]

__builtin_popcount 함수로 $1$ 인 비트만 바로 셀 수 있다. $X$ 를 2의 제곱수들의 합으로 표현했을 때 수의 개수는 2진수로 나타냈을 때 $1$ 인 비트의 개수와 동일하다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int x;
    cin >> x;
    cout << __builtin_popcount(x);
}

---

3. 풀이 정보

1. 수학 [Java]

언어	시간	메모리	코드 길이
Java 11	108 ms	14212 KB	388 B

2. 비트마스킹 [Java]

언어	시간	메모리	코드 길이
Java 11	108 ms	14284 KB	293 B

3. 수학 [C++]

언어	시간	메모리	코드 길이
C++ 17	0 ms	2020 KB	252 B

4. 비트마스킹 [C++]

언어	시간	메모리	코드 길이
C++ 17	0 ms	2020 KB	178 B

---