1. Bit Masking을 이용하여 각 자리에 숫자가 있는지 확인하는 방식을 이용한다. 2. 이 중 길이가 K이면서, N번째 부분 집합을 카운트한다.
Bit Masking bit 연산을 통해 각 자리에 숫자가 있는가를 확인하는 방법
솔직히 나도 한번에 이해가 되지 않았다.
예를 들어서, 3이라는 숫자가 있으면, 2진수로 0b0011로 표현할 수 있다. 이는 첫 번째, 두 번째 자리에 1, 세 번째, 네 번째 자리에 0이 있어 & 연산을 하면 첫 번째와 두 번째 자리에 숫자를 찾을 수 있다.
이와 같은 방식으로 부분 집합 {1,2} 를 찾을 수 있으며, 이를 이용하면 모든 경우의 수의 부분 집합을 구할 수 있다.
Code
for test_case in range(1, int(input()) +1):
N, K = map(int, input().split())
A = list(range(1, 13))
count = 0
# N개 까지의 부분집합 개수까지 반복
for i in range(1<<12):
resu = 0
arg = 0
# 0부터 N-1 까지
for j in range(12):
# 부분집합이 존재한다면
if i & (1<<j):
# 값의 합과 갯수
resu += A[j]
arg += 1
if resu == K and arg == N:
count += 1
print(f'#{test_case} {count}')
