[백준/파이썬] 1182번: 부분수열의 합

 

Happy Thanksgiving (출처:google)

-문제

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

1182번: 부분수열의 합

 

-풀이(1): 완전탐색

최대 20개의 원소로 이루어진 전체 수열이 주어질 수 있고 문제는 2초 안에 풀이 해야 해요.

20개의 원소가 주어졌을 때(상한) 추출할 수 있는 모든 부분 수열의 경우의 수는 2^20 -1 개에요.

 

2^10 은 대략 1000과 유사하므로 상한의 경우에 확인해야 할 모든 경우의 수는 약 100만 가지가 된다는 것을 알 수 있어요.

또, 각각의 경우의 수에서는 부분 수열의 원소들을 모두 더하고 이것이 S와 같은지만 판단하면 되므로 완전탐색으로 여유롭게 문제를 풀이 할 수 있어요,

 

따라서 아래와 같이 dfs를 이용해 모든 부분 수열들을 구하고 각 수열마다 그 합이 S가 되는지 판단하는 연산만 반복해주면 돼요.

 

-소스코드(1): 완전탐색

import sys
input = sys.stdin.readline

n, g = map(int, input().split())
given = list(map(int, input().split()))

result = 0
coor = []
def choice(i, fin):
    global result 
    
    if i == fin:
        cnt = 0
        for j in coor:
            cnt += given[j]
        if cnt == g:
            result += 1
        return
            
    elif i == 0:
        for j in range(n):
            coor.append(j)
            choice(i+1, fin)
            coor.pop()
            
    else:
        for j in range(n):
            if j > coor[-1]:
                coor.append(j)
                choice(i+1, fin)
                coor.pop()
                
for i in range(1, n + 1):
    choice(0, i)
    
print(result)

 

-풀이(2): 깔끔한, 효율적인 풀이

 두번째 방법은 풀이(1)과 같이 모든 경우의 수를 판단한다는 점에서 결을 같아요.

하지만 index를 하나하나 증가시키며 부분 수열의 모든 원소를 더하는 연산을 반복하지 않고 원소 하나 하나와의 덧셈만으로 합이 S가 되는지를 판단해서 훨씬 효율적으로 문제를 풀이해요.

 

-소스코드(2): 깔끔한, 효율적인 풀이

n, g = map(int, input().split())
given = list(map(int, input().split()))

result = 0
coor = []
def choice(idx, target):
    global result 
    if idx == n:
        return
    for i in range(idx, n):
        if given[i] ==target:
            result += 1
        
        choice(i + 1, target- given[i])
    
    
choice(0, g)
print(result)