BOJ 11723: 집합

www.acmicpc.net/problem/11723

11723번: 집합

문제 설명

어떤 집합(1~20까지 있음)이 있다고 가정할 때, 그 집합에 대한 일련의 연산들을 처리하는 문제이다.

 

문제 풀이

집합이라는 이름만 듣고 허겁지겁 다른 집합 관련 알고리즘들을 떠올렸던 것 같다.

사실 직접 비슷한 집합 구조를 구현하고 문제를 풀어도 틀리지는 않을 것 같다.

다만 그렇게 구현하려면 많이 귀찮기도 하고 요소가 20개 정도인 집합에 적용하기에는 비효율적이다.

 

집합의 요소가 20개로 한정되어 있고, 그것이 있거나(1) 없거나(0)만 처리하면 되는 부분에 주목하자.

이를 고려하면 해당 문제는 비트마스크로 쉽게 풀어줄 수 있다.

집합을 20자리 00000.. 으로 표현하고, 이때 어떤 요소가 있고 없고를 1, 0 으로 처리하는 것이다.

그리고 문제에서 나오는 연산들을 전부 비트 연산으로 처리하면 쉽고 빠르게 구현할 수 있다.

 

 

소스 코드

github.com/onaeonae1/ProblemSovling/blob/master/BOJ%2011723.cpp

onaeonae1/ProblemSovling

 

노트

*사실 동아리에서 비트마스크 문제를 풀자고 해서 해당 문제를 풀게 되었다. 즉, 비트마스크라는 것을 알고 풀었다.

*다른 문제를 접해도 비트마스크 문제인지 판별하려면 길이가 고정되어 있고, 0혹은 1로만 표현할 수 있는지를 고려하자