4837. [파이썬 S/W 문제해결 기본] 2일차 - 부분집합의 합

문제의 저작권은 SW Expert Academy에 있습니다.

 

 

def powerset(n, s):      # n: 원소의 갯수, s: 현재depth
    global K, cnt, A
    if s == 13 :
        return
 
    a = sum(A)
    if n == a:          # Basis Part
        sumt = 0
        for i in range(len(A)):
            if A[i] == 1:
                sumt += data[i]
        if sumt == K:
            cnt+=1
 
    else:               # Inductive Part
        A[s] = 1        # k번 요소 O
        powerset(n, s + 1)  # 다음 요소 포함 여부 결정
        A[s] = 0       # k번 요소 X
        powerset(n, s + 1)  # 다음 요소 포함 여부 결정
 
 
TC= int(input())
for tc in range(1, TC+1):
    N, K = map(int, input().split())
    cnt = 0
    data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
    A = [0]*13
    powerset(N, 0)
 
    print("#%d %d"%(tc, cnt))

 

나는 재귀로 풀었다.

나중에 재귀 배우고 푸는 것을 추천한다.

위 방법은 부분집합으로 푼 방법인데, 역량테스트 치는 사람들은 부분집합 재귀에 대해서 공부해 보는 것도 좋다.

 

위의 코드로 작성할 때 주의할 점은 A에 [0] 숫자를 13개 주는 것이다.

대입 후에 s+1로 재귀하기 때문에 사실 상 재귀 첫부분은 s+1이 아니라 s 부분을 검사하는 것이라는 것을 잊지말자