[백준] 14225 부분 수열의 합

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

import sys
n = int(input())
init_arr = map(int, input.split())
plus_arr = []
for i in range(len(init_arr)) :
    for j in range() :
        plus_arr.append(init_arr[i] + init_arr[j])
set_data = set(plus_arr)
list_data = list(set_data)
init_arr.extend(list_data)
print(init_arr)

 

내가 처음 접근했던 방식은 일단 굉장히 robust하게.. 수열을 합치는 느낌이다.

그런데 부분 수열의 합으로 나올 수 "없는" 가장 작은 자연수 를 어떻게 구할 지가 다소 어렵게 느껴졌었다.

 

n = int(input())
num = list(map(int,input().split()))
visited = [0]*10000000

def dfs(idx,sum) :
    if idx == n : # 종료 조건
       return
    sum += num[idx]
    visited[sum] = 1
    dfs(idx+1, sum) # 현재 숫자를 포함하는 경우
    dfs(idx+1, sum-num[idx]) # 현재 숫자를 포함 안하는 경우

dfs(0,0)
print(visited[1:].index(0)+1)

그래서 DFS로 풀 수 있는 코드를 공부해보자면 다음과 같다.

 

 

 

* 이 문제를 왜 DFS로 풀어야 하는가? 가능한 모든 조합을 찾아야 하므로