[Python] 백준 / 부분 수열의 합 / 14225번 / 브루트포스

문제

부분 수열의 합 문제 링크

수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오.

예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다.

입력

첫째 줄에 수열 S의 크기 N이 주어진다. (1 ≤ N ≤ 20)

둘째 줄에는 수열 S가 주어진다. S를 이루고있는 수는 100,000보다 작거나 같은 자연수이다.

3
5 1 2

출력

첫째 줄에 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력한다.

4

접근 방식

처음에는 방문처리를 활용하여 최대 길이만큼 수열을 만드는 과정에서 부분 합들을 구하는 방식으로 풀었으나 이는 O(n^n) 방법이였기 때문에 시간초과가 걸렸다

n = int(input())

num_list = list(map(int,input().split()))

partial_sum=[False]*(n*100000+1)

visited = {}

for num in num_list:
    if num not in visited:
        visited[num] = 1
    else:
        visited[num] += 1

def cal(now_depth,  visited, sub_sum):
    
    if now_depth == n :
        partial_sum[sub_sum] = True 
        return 

    for num in set(num_list):
        if visited[num] > 0:
            sub_sum += num
            partial_sum[sub_sum] = True
            visited[num] -= 1
            cal(now_depth+1,  visited, sub_sum)
            visited[num] += 1
            sub_sum -= num

cal(0,visited, 0)

i = 1
while True:
    if partial_sum[i] == True:
        i += 1
    else:
        print(i)
        break

위의 코드는 정답은 구했지만 시간초과가 났던 코드이다

1. 입력받은 숫자과 개수를 key-value로 하는 딕셔너리를 만든다 (중복 숫자가 있을 시 시간복잡도를 줄이기 위해)

2. 재귀함수에서 입력받은 숫자를 중복없이 반복문으로 접근한다

3. 접근한 숫자가 방문리스트에 남아있으면 sub_sum에 더한 값을 부분 합 리스트의 인덱스로 활용하여 True로 바꾼 후 방문 리스트의 값을 -1 하고 재귀함수로 깊이+1, 방문리스트, sub_sum을 넘겨준 뒤 다시 (방문 리스트 값 +1, sub_sum -= 접근한 숫자 )를 해준다

4. 부분합 리스트를 인덱스 1부터 접근하여 False 값이 나왔을 때 출력하고 break한다

n이 3개고
5, 1, 2를 받았을 때 다음과 같이 3^3 만큼 계산하게 된다

• 두 번째 방법으로 문제를 해결한 풀이이다

단순하게 숫자 리스트를 처음부터 하나씩 접근하여 숫자를 사용하거나 사용하지 않는 두 가지 경우로 재귀를 구성해 나간다
시간 복잡도 O(2^n)

그림으로 표현하면 다음과 같다

코드

n = int(input())

num_list = list(map(int,input().split()))

partial_sum=[False]*(n*100000+1)


def cal(i, sub_sum):
    if i == n:
        partial_sum[sub_sum] = True
        return
    cal(i+1,sub_sum+num_list[i])
    cal(i+1,sub_sum)
    

cal(0,0)

i = 1
while True:
    if partial_sum[i] == True:
        i += 1
    else:
        print(i)
        break