[Python][SWEA] 2817. 부분 수열의 합 D3

 

SW Expert Academy

---

 

🗒️파이썬 코드 풀이

T = int(input())
for tc in range(1,T+1) :
    N,K = map(int,input().split())
    lst = list(map(int,input().split()))
    ans,sum,n = 0,0,0
    
    def dfs(n,sum) :
        global ans
        if sum == K : # 총 합이 K 일때 
            ans += 1
            return 
        if n >= N: # n이 배열 크기만큼 도달 할 경우
            return 
        if sum > K : # 합이 K를 넘어선 경우 
            return
        
        dfs(n+1,sum+lst[n])
        dfs(n+1,sum)

    dfs(n,sum)
    print(f"#{tc} {ans}")

 

1. 각 리스트의 값들을 넣을지 말지를 생각하면 됨

2. N<50 ( 50 넘어가면 이진트리 하기 어려움) 이므로 dfs로 진행

3. n == N 일 경우만 해도 되지만, 효율성을 위해 가지치기 (sum>K)

4. sum == K 인 경우가 위에 가야함 (만일 if문의 n>=N 아래이면, ans+=1은 실행도 못하고 return)

 

📌다른 방법 

 if n == N :
        if sum == K :
            ans += 1
        return

이 코드에서는 가지치기가 없는거 빼고는 내가 쓴 코드와 거의 똑같다.  

다만, 내가 생각하기에 재귀함수에 기본은 n == N의 조건을 충족 할 때 return을 하는 것이다.

주어진 N의 범위 자체가 크지 않기 때문에 뭘 해도 실행에는 문제가 없다.

---

📚문제

A1, A2, ... , AN의 N개의 자연수가 주어졌을 때, 최소 1개 이상의 수를 선택하여 그 합이 K가 되는 경우의 수를 구하는 프로그램을 작성하시오.


[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 2개의 자연수 N(1 ≤ N ≤ 20)과 K(1 ≤ K ≤ 1000)가 주어진다.

두 번째 줄에는 N개의 자연수 수열 A가 주어진다. 수열의 원소인 N개의 자연수는 공백을 사이에 두고 주어지며, 1 이상 100 이하임이 보장된다.


[출력]

각 테스트 케이스마다 ‘#x ’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 부분 수열의 합이 K가 되는 경우의 수를 출력한다.