[#1182] 부분수열의 합

❓ Question

📖 Before Start

조합과 순열, 이 두개는 정말 계속해서 나오는 친구들이라고 생각한다.

지금은 고등학교 과정에서 수열을 배우지 않는다는 소식을 들었을 때, 필자는 정말로 큰 충격에 빠졌다.
'그럼, 수열을 전혀 모르는 사람들은 이 문제를 어떻게 풀 수 있을까?' 라는 생각이 잠깐 들 정도로 말이다.

✒️ Design Algorithm

이 문제는 비교적 쉬운 편에 속했다. 이건 무조건 조합 (Combination) 을 쓰는 문제다!

순열과 조합을 프로그래밍에서 만나게 될 줄은 몰랐는데, 역시 인생은 어떻게 될 지 모르는 법이라고 했다.
다행이도 필자는 이 문제를 만나기 전에 다른 곳에서 itertools 라이브러리의 존재를 알게 된 상태였다.
내가 직접 순열과 조합을 구현하지 않아도 라이브러리에서 해주다니, Python은 역시 사기가 분명하다.

아래는 필자가 문제를 풀기 전 작성한 알고리즘 설계이다.

첫째 줄에는 정수의 개수 N, 그리고 기준이 되는 정수 S가 주어진다.
두번째 줄에는 N개의 정수가 빈 칸을 사이에 두고 연속으로 주어진다.

1. N개의 정수 중 1에서 N-1개 를 뽑아 나온 조합들의 합을 구한다.
2. 그 합이 S와 같다면 경우의 수를 나타내는 변수에 1을 추가한다.

💻 Making Own Code

import sys
import itertools as itr

n, s = map(int, sys.stdin.readline().split())
data, result = list(map(int, sys.stdin.readline().split())), 0

for i in range(1, n+1):
    for c in itr.combinations(data, i):
        if sum(c) == s:
            result += 1
print(result)

순열과 조합은 itertools 라이브러리를 사용하는 것이 최선의 풀이라고 생각한다.

이번 문제도 itertools 의 combination(data, number) 를 활용하여 문제 풀이에 성공하였다.
다만, 필자는 부분수열이 자기 자신도 포함한다는 사실을 모른 채 제출을 했다가 빠꾸를 한번 먹었다.

여러분들은 필자의 경우처럼 실수하는 일 없이, 잘 풀이하여 문제를 해결하기 바란다.