[python] 백준 1182번 부분수열의 합

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

1182번: 부분수열의 합

 

 

💻 코드

 

import sys
from itertools import combinations

input = sys.stdin.readline

n, s = map(int, input().split())
number = list(map(int, input().split()))
count = 0

for i in range(1, n + 1):
    result = list(combinations(number, i))
    for num in result:
        if (sum(num) == s):
            count += 1

print(count)

 

 

📝 풀이

 

이 문제는 조합으로 쉽게 풀 수 있었다. 입력한 수열에서 가능한 모든 조합을 구하고 그 각각의 합을 구해서 s와 같으면 카운트를 해주는 방법이다. 

 

예시)

n = 5, s = 0 이면,

5개의 정수로 이루어진 수열이 있고, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 합이 0가 되는 경우의 수를 구하는 것이다.

 

입력한 수열 number : [-7, -3, -2, 5, 8]

 

 

list(combinations(number, i))는 number 리스트에서 i개의 원소 조합을 만들어내는 함수로 가능한 모든 조합을 구해준다.

 

 

i가 1일 때,

1개의 원소 조합으로 이루어진 리스트가 만들어진다.

result : [(-7), (-3), (-2), (5), (8)]

 

i가 2일 때,

2개의 원소 조합으로 이루어진 리스트가 만들어진다.

result : [(-7, -3), (-7, -2), (-7, 5), (-7, 8), (-3, -2), (-3, 5), (-3, 8), (-2, 5), (-2, 8), (5, 8)]

 

i가 3일 때,

3개의 원소 조합으로 이루어진 리스트가 만들어진다.

 result : [(-7, -3, -2), (-7, -3, 5), (-7, -3, 8), (-7, -2, 5), (-7, -2, 8), (-7, 5, 8), (-3, -2, 5), (-3, -2, 8), (-3, 5, 8), (-2, 5, 8)]

 

...(i가 4일 때, i가 5일 때 생략)

 

 

 

이 result 리스트에 있는 각 수열의 원소의 합이 s가 된다면 count를 해준다.

 

i가 1일 때,

[(-7), (-3), (-2), (5), (8)] ➡ 0이 되는 값이 없음 count = 0

 

i가 2일 때,

[-10, -9, -2, 1, -5, 2, 5, 3, 6, 13] ➡ 0이 되는 값이 없음 count = 0

 

i가 3일 때,

[-12, -5, -2, -4, -1, 6, 0, 3, 10, 11] ➡ 0이 되는 값이 1개 있다! count = 1

 

i가 4일 때와 i가 5일 때도 마찬가지이다.