백준 1182 - 부분수열의 합(Python)

문제

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

풀이

import itertools as it
n,s = map(int,input().split())
l = input().split()
cnt = 0
for i in range(1,n+1):
    for c in it.combinations(l,i):
        if sum(map(int,c)) == s:
            cnt+=1
print(cnt)

파이썬의 itertools를 사용하여 조합을 구하고 합을 비교했다.

부분수열이라길래 초반에는 연속된 수열만 가능한 줄 알고 해당 경우의 수만 구했지만,

검색해보니 부분수열은 수열에서 임의의 원소를 뽑아서 기존 수열의 순서대로 배치만 하면 되는거라 연속될 필요가 없다는 것을 알게되었다. 

이후 itertools를 이용하여 간단히 구현해주었다.