[백준] 1182: 부분수열의 합

1182번: 부분수열의 합

 

import sys
from itertools import combinations
n, s = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
def solution(n, s, arr):
    count = 0
    for i in range(1, n+1):
        for num in combinations(arr, i):
            if sum(num) == s:
                count += 1
    return count
print(solution(n, s, arr))

부분 수열의 합이 s가 되는 경우를 구해야 하는 완전탐색 문제입니다.

부분수열이니까 순서를 고려하지 않아야하고, 모든 길이의 부분수열을 모두 고려해주어야 합니다.

각 원소를 선택하거나 선택하지 않거나 둘 중 하나를 고려해 주어야 하기 때문에 O(2^N)의 시간복잡도를 가지게 됩니다.

N =3인 부분집합을 만든다고 할 때 아래와 같이 됩니다.

a	b	c	부분집합
x	x	x	공집합
o	x	x	a
x	o	x	b
x	x	o	c
o	o	x	a, b
o	x	o	a, c
x	o	o	b, c
o	o	o	a, b, c

8가지가 나오게 되는데 이는 2^3=8을 만족합니다.

문제의 조건에서 N은 20이하라고 했으니 2^20=1,048,576 백만이 조금 넘습니다. 제한시간 2초안에 해결할 수 있습니다.

파이썬은 1초에 1억번 정도 연산이 가능하다고 합니다. 만일 N의 최댓값이 30이라면 2^30=1,073,741,824(10억)이라 시간 초과가 걸리게 됩니다.