Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

33. 동적 계획법3

비트마스크를 배우고, 동적 계획법에 적용해 봅시다. 그 후에는 선형이 아니라 원형으로 구성된 문제를 다룹니다.

Java / Python

1. 집합

11723번

비트마스크 DP에 대해 다루기 전에, 일단 비트마스크부터 다뤄 봅시다.

이번 문제는 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 문제이다.

int 자료형을 선언하면, 4바이트(4 * 8bit)를 메모리에 할당받아, 총 32가지 경우에 대해 참, 거짓을 판단할 수 있게 된다. 이 문제의 경우, 20개의 숫자의 유무를 저장할 수 있어야 하는 데 int 자료형 변수 1개로, 32개면 충분하다.

bit_set = 00000000 00000000 00000000 00000000(2)로 메모리에 할당받는다.
아래와 같이, 총 0~31까지 수의 집합을 나타낼 수 있다.

2^0자리 ▶ 0의 true, false

2^1자리 ▶ 1의 true, false

2^2자리 ▶ 2의 true, false

...

2^30자리 ▶ 30의 true, false

2^31자리 ▶ 31의 true, false

비트 연산 이용

• Java

import java.io.*;
import java.util.*;

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

		int N = Integer.parseInt(br.readLine());
		int bit_set = 0;
		while (N-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String op = st.nextToken();
			int num;

			// 연산
			switch (op) {
				case "add":
					num = Integer.parseInt(st.nextToken());
					bit_set |= (1 << (num - 1));
					break;
				case "remove":
					num = Integer.parseInt(st.nextToken());
					bit_set = bit_set & ~(1 << (num - 1));
					break;
				case "check":
					num = Integer.parseInt(st.nextToken());
					sb.append((bit_set & (1 << (num - 1))) != 0 ? "1\n" : "0\n");
					break;
				case "toggle":
					num = Integer.parseInt(st.nextToken());
					bit_set ^= (1 << (num - 1));
					break;
				case "all":
					bit_set |= (~0);
					break;
				case "empty":
					bit_set &= 0;
					break;
			}
		}
		bw.write(sb.toString());

		bw.flush();
		bw.close();
		br.close();
	}
}

• Python

import sys
input=sys.stdin.readline
bit_set = 0
for _ in range(int(input())):
    op = input().split()
    if op[0]=='add' : bit_set |= 1 << int(op[1])
    if op[0]=='remove' : bit_set &= ~(1 << int(op[1]))
    if op[0]=='check' : print(1 if bit_set & (1 << int(op[1])) else 0)
    if op[0]=='toggle' : bit_set ^= (1 << int(op[1]))
    if op[0]=='all' : bit_set = (1<<21)-1
    if op[0]=='empty' : bit_set = 0