백준 1182번 파이썬 _ 부분수열의 합

www.acmicpc.net/problem/1182

1182번: 부분수열의 합

• 문제유형 : 브루트포스, 백트래킹
• 문제풀이
  • N의 범위가 최대 20이므로 완전탐색으로 모든 부분집합을 다 구해도 2^20승 (1,048,576)이므로 전체 부분집합을 다 구하고 조건에 맞는지 확인하는 완전탐색을 이용해도 됨 (파이썬에서 1초에 대략 2천만번의 연산이 가능하므로)
  • 여러 풀이방법이 있음 (재귀, 멱집합 등등) 
  • 나는 원소의개수가 1부터n까지 증가하도록 조합을 사용하여 모든 부분집합을 구해서 풀었다.
  • 파이썬의 itertools라이브러리 이용 (combination)
  • itertool의 permutaions 와 combinations는 완전탐색에 많이 쓰이므로 꼭 기억할것
    • permutations - 순열 (중복x)
    • combinations - 조합 (중복x)
• 정답코드
  • 조합을 이용한풀이

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

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

count = 0
#정수이므로 갈수록 커지는게 아니고 작아질수도있고 커질수도 있음

#길이가 1인것에서부터 n인것까지

for i in range(1,n+1):
    per = combinations(data,i)
    for j in list(per):
        if sum(j) == s:
            count += 1
print(count)

 

 

• dfs를 이용하여 재귀적으로 푼 풀이 
  • 해당원소를 포함하는 경우/ 포함하지 않는경우로 인덱스가 늘어감에따라 가지가 뻗어나가는 형태

import sys
input = sys.stdin.readline
def dfs(idx, sum):
    global cnt
    if idx >= n:
        return
    sum += s_[idx]
    if sum == s:
        cnt += 1
    dfs(idx + 1, sum - s_[idx])
    dfs(idx + 1, sum)
n, s = map(int, input().split())
s_ = list(map(int, input().split()))
cnt = 0
dfs(0, 0)
print(cnt)

출처: https://pacific-ocean.tistory.com/306

•