<BOJ>1094번: 막대기

문제

1094번: 막대기

접근

• 간단한 수식으로 풀 수 있는 문제라곤 하는데, 막대기를 항상 절반으로 자르기 때문에 비트마스크로도 풀 수 있다.
• 64cm 막대를 2진수로 표현하면 1000000가 되는데 이를 가지고 Xcm을 만들자.
• 집합으로 생각해서 원소를 포함하는지 여부를 계산하면 된다. (쉽게 말해 X를 2진수로 만들었을 때, 1의 개수를 계산하면 된다.)

내 코드

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 count = 0;
        for (int i = 0; i <= 6; i++) {
            if ((x & (1<<i)) != 0) count++;
        }
        System.out.println(count);
    }
}

for 루프는 64의 비트 수 만큼 도는데, 루프 내에서 (x & (1<<i))로 판단하면 된다.

📌 비트마스크(bitmask)?

정수의 2진수 표현을 자료 구조로 쓰는 기법을 말한다.

장점

• O(1)에 해결 할 수 있는 더 빠른 수행 시간
• 더 간결한 코드: 다양한 집합 연산들을 반복문 없이 한 줄에 쓸 수 있음.
• 더 작은 메모리 사용량
• 연관 배열을 배열로 대체: C++의 경우 map<vector<bool>, int>를 비트마스크를 사용해 단순히 int[]로 만들 수 있다.

연산

비트마스크를 이용한 집합의 구현 예제

한 피자집에는 0부터 19까지의 번호를 갖는 스무 가지의 토핑이 있으며, 주문 시 토핑을 넣기 or 넣지 않기를 선택할 수 있다. 이렇게 하면 한 피자의 정보는 스무 종류의 원소만을 가지는 집합이 되고, 비트마스크를 이용해 표현할 수 있게 된다.

1. 공집합과 꽉 찬 집합 구하기

int fullPizza = (1 << 20) - 1;

2. 원소 추가

toppings |= (1 << p);

3. 원소의 포함 여부 확인

if (toppings & (1 << p)) System.out.println("peperoni is in");

4. 원소의 삭제

toppings &= ~(1 << p);

5. 원소의 토글

toppings ^= (1 << p);

6. 두 집합에 대해 연산하기

int added = (a | b); // a와 b의 합집합
int intersection = (a & b); // a와 b의 교집합
int removed = (a & ~b); // a에서 b를 뺀 차집합
int toggled = (a ^ b); // a와 b중 하나에만 포함된 원소들의 집합

7. 집합의 크기 구하기

public int bitCount(int x) {
    if (x == 0) return 0;
    return x % 2 + bitCount(x/2);
}

또는 Integer.bitCount(toppings) 사용

8. 최소 원소 찾기
   2의 보수 연산을 활용하여 다음과 같이 작성한다.

int firstTopping = (toppings & -toppings);

또는 Integer.numberOfTrailingZeros(toppings) 사용

9. 최소 원소 지우기

toppings &= (toppings - 1);

10. 모든 부분 집합 순회하기

for (int subset = pizza; subset; subset = ((subset-1) & pizza)) {
    // subset은 pizza의 부분집합
}

Reference

• 프로그래밍 대회에서 배우는 알고리즘 문제해결전략(a.k.a 종만북)