[SWEA] 4837. 부분 집합의 합 - Python

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

< 📝 문제 >

1부터 12까지의 숫자를 원소로 가진 집합 A가 있다. 집합 A의 부분 집합 중 N개의 원소를 갖고 있고, 원소의 합이 K인

 

부분집합의 개수를 출력하는 프로그램을 작성하시오.

해당하는 부분집합이 없는 경우 0을 출력한다. 모든 부분 집합을 만들어 답을 찾아도 된다.

 

예를 들어 N = 3, K = 6 경우, 부분집합은 { 1, 2, 3 } 경우 1가지가 존재한다.

< ❓ 생각 >

부분집합의 구하면서 원소의 합을 확인해보기

< 💻 코드 >

# T : 테스트 케이스 수
T = int(input())
for tc in range(1,T+1):
    # N : 부분 집합 원소의 개수, K : 부분 집합 원소의 총 합
    N, K = map(int,input().split())

    # 1~ 12까지 숫자를 원소로 가진 집합
    arr = [i for i in range(1,13)]
    # 부분 집합의 원소의 개수가 N, 부분 집합 원소의 총 합이 K인 부분집합 개수
    result = 0

    # 모든 부분 집합 확인
    for i in range(1<<12):
        # 부분집합의 합
        sum_sub = 0
        # 부분집합
        subset = []
        for j in range(12):
            if i & (1<<j):
            # j번째 요소는 부분집합에 포함
                sum_sub += arr[j]
                subset.append(arr[j])

    # 부분 집합의 원소의 개수가 N, 부분 집합 원소의 총 합이 K인 부분집합 개수 구하기
        if len(subset) == N and sum_sub == K:
            result += 1

    print(f'#{tc} {result}')

< ❗ >

• & 연산자
  • i&(1<<j) : i의 j번째 비트가 1인지 아닌지를 검사한다.

# (1<<j)는 j번째 비트만 1

if i&(1<<j):
    print('i의 j번째 비트가 1')
else:
    print('i의 j번째 비트가 0')
    
    
# i가 5라면, 101(2)이므로
# 1<<0 : True
# 1<<1 : False
# 1<<2 : True