[Python] 백준 1182 부분수열의 합

 

문제 분석

• N개의 정수로 이루어진 수열
• 크기가 양수인 부분 수열 중 원소를 다 더한 값이 S가 되는 경우의 수를 구하라

 

풀이

1. 완전탐색이 가능할까?
   • 문제에서 수열의 개수는 n개, 총 최대 20개이다.
   • 이때 부분 수열을 만드는 경우의 수는 n개의 원소들에 대해 각 원소를 선택하느냐 / 아니냐로 정해진다.
     각각의 원소들이 부분 수열에 포함되는가 / 아닌가
   • 따라서 20개 원소에 대해 총 2^20가지의 부분 수열의 경우의 수가 존재한다.
   • 2^20 = 1,048,576개로 시간 제한 안에 모두 탐색해도 충분히 가능한 개수이다.
     
     모든 부분 수열 만들기
     • n개의 원소를 가진 수열에 모든 부분 수열 경우의 수를 어떠헥 만들 수 있는가
     • 0번 부터 n-1번까지의 원소들에 대해 배열에 포함 or 포함 X 이 과정을 재귀적으로 반복하면 된다.
       
       
     • 이 문제에서 부분 수열의 합을 찾아야 하기 때문에 현재까지 구한 수열의 합을 재귀로 넘겨주면서 탐색한다.
     • 현재까지의 합에서
       • 다음 원소를 합에 포함
       • 다음 원소를 합에 포함하지 않음
     • 이렇게 2가지의 경우를 재귀로 탐색해준다.
       
       
     • 이때 총 탐색한 원소가 N개에 도달하면 탐색 종료
     • 이후 현재 합이 s와 일치한다면 정답에 +1을 해준다.
       
       
     • 다만 이때 s가 0이라면 모든 원소를 선택하지 않은 경우가 포함될 수 있기 땜누에 이를 정답에서 한 개 빼주어야 한다.
2. combinations 활용

 

코드 설계

• 순서 x, 중복 x → 조합으로 합이 S가 되는 경우의 수
• 조합 : combinations

 

정답 코드

1. 완탐

import sys
input = sys.stdin.readline

n, s = map(int, input().split())
arr = list(map(int, input().split()))

ans = 0

def dfs(idx, total) :
    global ans
    if idx == n :
        if total == s :
            ans += 1
    dfs(idx+1, total)
    dfs(idx+1, total+arr[idx])

dfs(0,0) # 탐색 시작
if s == 0 :
    ans -= 1
print(ans)

2. combinations

import sys
input = sys.stdin.readline
from itertools import combinations

n, s = map(int, input().split())
nums = list(map(int, input().split()))
ans = 0

for i in range(1, n+1) :
    for com in combinations(nums, i) :
        if sum(com) == s :
            ans += 1

print(ans)