[ SW Expert Academy / 4837 ] 부분집합의 합

1. 문제 이해

입력값:
N (1 이상 12 이하)
K (1 이상 100 이하)

유의해야 할 점:
1. 1 부터 12까지의 숫자를 원소로 하는 집합 A

N : 부분집합의 원소 수
K : 부분집합 원소의 합

출력 값:
 제시된 원소수와 원소 합에 대응하는 부분집합의 수

 

2. 문제 풀이 법

사용한 방법: 부분집합 구하기

temp_sum - 부분집합 합
temp_cnt   - 부분집합 원소 수 

부분집합 합과 원소 수 구하는데,
만약 문제에서 제시한 합 또는 원소수를 초과 할 경우 break를 통해 해당 부분집합은 skip 하였다.

 

3. 어려웠던 점

부분집합 코드 

T = int(input())
for tc in range(1,T+1):
    N, K = map(int,input().split())
    result = 0 # 조건에 만족하는 부분집합의 수

    for i in range(1<<12):
        temp_cnt = 0 # 부분집합 원소 갯수
        temp_sum = 0  # 부분집합 원소
        for j in range(12):
            if i & (1<<j): # j 번째 비트가 1이면
                temp_sum += j+1 # 1 ~ 12
                temp_cnt += 1
                if temp_cnt > N or temp_sum > K:
                    break
        if temp_cnt == N and temp_sum == K:
            result += 1
    print(f'#{tc} {result}')

4. 배운 점

부분집합

 

5. 메모

 

+) 부분집합

 

arr = [ 2 ,3 , 5, 68, 89, 8]
n = len(arr) # 원소 수

for i in range(1<<n) # arr 부분집합 수
	for j in range(n) # 비트 비교 ( 원소 수 )
    	if i % (1<<j) # i의 j 번째 비트가 1이면 j번쨰 원소 출력 (부분집합에들어가는 원소 채택)
        	# 코드 적용