BOJ 1094 · 막대기

알고리즘 분류 : 시뮬레이션  

문제에 주어진 조건을 그대로 구현하는 문제다. X 길이를 만들기 위해 막대기를 자르고 이어붙인다. 막대기의 길이는 64부터 시작한다. 자르고 이어붙이는 방법은 우선 막대기의 총 길이 합이 X보다 크면, 반으로 자른다. 만약 반으로 자른 것 중 하나를 제외하고 더한 길이의 합이 X보다 크거나 같으면, 제외한 절반의 막대기를 버린다. 남은 막대기를 모두 더한 길이의 합이 X가 되지 않는다면 위 방법을 반복한다.

• 이 문제는 2진수 방법으로도 해결할 수 있다.
• 막대기는 64부터 시작하고, 막대기는 계속해서 절반으로 쪼개진다.
• 즉, 64, 32, 16, 8, 4, 2, 1 순으로 쪼개진다.
• 때문에 막대기 조각은 반드시 64, 32, 16, 8, 4, 2, 1의 조합으로 이루어져 있다.
• 이 숫자는 2^6, 2^5, 2^4, 2^3, 2^2, 2^1, 2^0의 조합이므로 7비트의 이진수와 같다.
• X에서 X & (1<<i) 연산을 통해 2^i 에서 1인 자릿수를 카운트하면, 그것이 정답이다.

---

C++ 소스코드

#include <cstdio>
#include <deque>
using namespace std;

int sum(deque<int> q) {
    int res = 0;
    for (auto k : q) res += k;
    return res;
}

int main() {
    int x;
    scanf("%d", &x);
    deque<int> dq;
    dq.push_back(64);
    while (sum(dq) != x) {
        int y = dq.front()/2; dq.pop_front();
        dq.push_front(y);
        if (sum(dq) < x) dq.push_front(y);        
    }
    printf("%d\n", (int)dq.size());
    return 0;
}

✓ 2진수 방법을 이용한 구현은 아래와 같다.

#include <cstdio>

int main() {
    int x;
    scanf("%d", &x);
    int cnt = 0;
    for (int i=0; i<=6; i++) {
        if (x & (1<<i)) cnt++;
    }
    printf("%d\n", cnt);
    return 0;
}

---

Python 3 소스코드

print(bin(int(input())).count('1'))

✓ 정수를 이진수로 바꿔주는 bin 함수와, 리스트에서 특정 원소의 개수를 세주는 count 함수를 이용하면 한 줄로 해결할 수 있다.

---

참고

• 백준 온라인 저지 : BOJ 1094