백준: 1182 부분수열의 합

문제

1182번: 부분수열의 합

 

문제 풀이

 N개의 정수로 이루어진 수열에서 부분 수열의 합이 S가 되는 경우의 수를 찾는 문제이다. 이는 조합을 구하고 발생한 각 조합 중 합이 S를 만족하는지 찾으면 되는 문제이다. N의 범위가 크지 않으므로, 단순히 DFS를 사용하여 문제를 풀 수 있다.

 

코드

DFS를 이용한 문제 풀이

from sys import stdin


def dfs(depth, subtotal):
    global answer

    if depth == n:
        return

    if subtotal + nums[depth] == s:
        answer += 1

    dfs(depth + 1, subtotal + nums[depth])
    dfs(depth + 1, subtotal)


if __name__ == "__main__":
    answer = 0
    n, s = map(int, stdin.readline().split())
    nums = list(map(int, stdin.readline().split()))
    dfs(0, 0)
    print(answer)

 가지를 뻗으면서 현재의 수를 선택하거나, 선택하지 않는 경우의 수로 나뉘게 된다. 또한 하나의 원소만 선택되는 것을 방지하기 위해 `if subtotal + nums[depth] == s`라는 조건이 필요하다.

 

itertools를 이용한 문제 풀이

from itertools import combinations

n, s = map(int, input().split())
nums = list(map(int, input().split()))
answer = 0
for i in range(1, n + 1):
    for case in combinations(nums, i):
        if sum(case) == s:
            answer += 1
print(answer)

 조합을 구하는 문제이므로 파이썬의 `itertools`를 활용하여 문제를 해결할 수 있다. 단, 특정 코딩테스트(ex: 삼성)에서는 사용이 불가능하므로, DFS를 이용한 문제 풀이를 활용하는 것이 좋다.