[Python] 1182번 : 부분수열의 합

 

문제 3줄 요약

1. N개의 정수로 이루어진 수열과 주어진 정수 S가 있다.

2. 수열의 원소들을 더하여 S를 만들고자 한다.

3. 주어진 수열의 원소들을 이용하여 S를 만들 수 있는 경우의 수를 구하여라.

 

 

처음 문제에 접근 하였을 땐,

투포인터를 이용하여

좌, 우 원소의 합이 S보다 클 때, 작을 때를 나누어

원소들을 더해주는 방식으로 접근하였다.

 

하지만

투포인터로는 모든 경우의 수를 탐색하긴 어렵다는 글을 확인한 후

브루트포스 알고리즘을 이용하였다.

 

모든 조합의 경우의 수를 더해보며

타겟인 S와 같은 경우를 카운트 해주었다.

 

from sys import stdin
# 조합 라이브러리
from itertools import combinations

if __name__ == "__main__":
    N, S = map(int, stdin.readline().split())
    num_list = list(map(int,stdin.readline().split()))

    answer = 0
    for cnt in range(1,N+1):
    # combinations(List, 원소의 수)
    # ex) combinations([1,2], 2) => [1,2], 중복 x([2,1])
        for numbers in combinations(num_list,cnt):
            if sum(numbers) == S:
                answer += 1

    print(answer)

 

풀이는 매우 간단하지만,

부분 수열이라는 것에서

순서대로 값을 더해야하는지 좀 애매했던 부분도 있었고,

주어지는 정수의 갯수가 20 개 이하라는 점에서

투포인터 보다는 브루트포스 알고리즘이 더 코드는 간단하였다.

 

끝!