부분 집합의 합 Python(SW Expert Academy)

난이도 : D3

문제번호 : 4837

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVF-WqqecDFAWg#

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

1부터 12까지의 숫자를 원소로 가진 집합 A가 있다. 집합 A의 부분 집합 중 N개의 원소를 갖고 있고, 원소의 합이 K인 부분집합의 개수를 출력하는 프로그램을 작성하시오. 해당하는 부분집합이 없는 경우 0을 출력한다. 모든 부분 집합을 만들어 답을 찾아도 된다.   예를 들어 N = 3, K = 6 경우, 부분집합은 { 1, 2, 3 } 경우 1가지가 존재한다.

 

입력

첫 줄에 테스트 케이스 개수 T가 주어진다.  ( 1 ≤ T ≤ 50 )   테스트 케이스 별로 부분집합 원소의 수 N과 부분 집합의 합 K가 여백을 두고 주어진다. ( 1 ≤ N ≤ 12, 1 ≤ K ≤ 100 )

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

예시

입력	출력
3 3 6 5 15 5 10	#1 1 #2 1 #3 0

2. 문제풀이

---

파이썬 Intermediate 2일차 문제입니다. 부분집합의 합 문제인데요 주어진 숫자들을 조합하여 더해서 원하는 숫자를 몇개까지 만들수 있냐를 물어보는 문제였습니다. 따라서 조합을 만들줄 알아야하는데 dfs를 이용하여 문제를 풀었습니다. dfs가 궁금하다면 아래의 링크로 이동해주세요

 

 

---

3. 소스코드

def recursion(count, targetNum, currentCount = 0, result = 0, temp_sum = 0, is_index = 0):
    #리턴조건
    if currentCount >= count : return result
    #1부터 12까지
    for k in range(is_index, 12):
        #임시합을 더해본다.
        t_s = temp_sum+k+1
        #더한값이 타겟넘과 같고 더한 횟수가 목표횟수와 같다면 결과에 추가 
        if t_s == targetNum and count == currentCount+1: return result + 1
        #재귀로 계산한다.
        result = recursion(count, targetNum, currentCount+1,result, t_s, k+1)
    return result
 
T = int(input())
for t in range(1, T+1):
    count, targetNum = map(int, input().split())
    result = recursion(count, targetNum)
    print("#{} {}".format(t, result))