[C++] 알고스팟/비트마스크 - 졸업 학기

문제 링크

https://algospot.com/judge/problem/read/GRADUATION

algospot.com :: GRADUATION

 

졸업에 필요한 과목을 듣는데 다녀야 할 최소 학기를 구하는 문제입니다.

전공과목, 학기에 대한 정보가 주어졌을 때 이 값들을 비트 마스크를 사용하여 값을 저장하고 변경함으로써 실행 시간을 줄일 수 있습니다.

 

 

문제를 풀기전에 기본적으로 알아두면 좋은 비트 연산자와 비트마스크 입니다.

 

비트 연산자

코드	설명	예시
a & b	a, b의 AND 연산	4 & 2 = 100 & 010 = 000
a | b	a, b의 OR 연산	4 | 2 = 100 | 010 = 110
a ^ b	a, b의 XOR 연산	4 ^ 2 = 100 ^ 010 = 110
~a	a의 NOT 연산	~4 = ~100 = 011
a << b	a를 왼쪽으로 b비트 시프트	4 << 2 = 10000
a >> b	a를 오른쪽으로 b비트 시프트	4 >> 2 = 1

 

비트마스크

코드	설명	예시
a |= (1 << b)	정수 a의 b번 비트를 켬	1000 |= (1 << 2) = 1100
if( a & (1 << b) )	정수 a의 b번 비트가 켜있는지 확인 (포함 시 1<<b, 아닐 시 0)	1000 & (1 << 2) = 0 1000 & (1 << 3) = 8
a &= ~(1 << b)	정수 a의 b번 비트를 끔	111 &= ~(1 << 0) = 110
a ^= (1 << b)	정수 a의 b번 비트를 토글	111 ^= (1 << 1) = 101
(a & -a)	a의 최소원소 반환 (10100 의 최소 원소 = 100 = 4)	( 10100 & -10100) = 100
a &= (a-1)	a의 최소원소 지우기	10100 &= (10100 - 1) = 10000

 

 

주어지는 입력 값이 많아 헷갈리므로 각 입력 값들의 의미를 자세히 파악해야 합니다.

아래는 첫번째 테스트케이스에 사용되는 입력 값들입니다.

 

구현 코드