[PS] 백준 1094번 막대기

이번에는 백준 1094번 막대기 문제를 풀어보았습니다.

처음에는 문제 그대로 막대를 계속 반으로 자르면서 시뮬레이션을 해야 하나 생각했습니다.

하지만 문제를 다시 읽어보니 결국 사용할 수 있는 막대의 길이는 1, 2, 4, 8, 16, 32, 64뿐이라는 점을 알 수 있었습니다.

즉, X를 만들기 위해 필요한 막대의 개수는 X를 2의 거듭제곱들의 합으로 나타냈을 때 사용되는 막대의 개수와 같다는 것을 이용하여 구현하였습니다.

---

문제 설명

처음에는 길이 64cm인 막대 하나가 있습니다.

막대를 절반씩 잘라가며 길이 X를 만들려고 합니다.

최종적으로 X를 만들기 위해 필요한 막대의 개수를 구하는 문제입니다.

---

풀이 아이디어

문제에서 막대를 절반씩 자르기 때문에 만들어질 수 있는 막대의 길이는 다음과 같습니다.

1, 2, 4, 8, 16, 32, 64

결국 X는 위 길이들의 합으로 표현됩니다.

이는 X를 이진수로 표현한 것과 동일합니다.

따라서 X의 이진수에서 1의 개수만 세면 사용해야 하는 막대의 개수를 바로 구할 수 있습니다.

---

코드

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

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;

    int cnt = 0;

    for (int i=0; i<8; i++) {
        if (N & (1 << i))
            cnt++;
    }

    cout << cnt << '\n';

    return 0;
}

---

풀이 흐름

1. X를 입력받습니다.
2. 각 비트를 확인합니다.
3. 현재 비트가 1이라면 막대 하나를 사용하는 것이므로 개수를 증가시킵니다.
4. 모든 비트를 확인한 뒤 개수를 출력합니다.

---

구현 포인트

1. 막대의 길이와 이진수

막대를 절반씩 자르면 만들 수 있는 길이는

1, 2, 4, 8, 16, 32, 64

뿐입니다.

즉, X를 이러한 막대들의 합으로 표현하는 것은 X를 이진수로 표현하는 것과 같습니다.

예를 들어

23 = 16 + 4 + 2 + 1

이므로 필요한 막대는 4개입니다.

---

2. 비트 확인

각 비트가 1인지 확인하였습니다.

if (N & (1 << i))
    cnt++;

현재 비트가 1이라면 해당 길이의 막대를 사용하는 것이므로 개수를 증가시켰습니다.

---

3. 막대 개수 출력

모든 비트를 확인한 뒤 1의 개수를 출력하였습니다.

cout << cnt << '\n';

결국 이진수에서 1의 개수가 문제에서 요구하는 막대의 개수가 됩니다.