백준: 14225 부분수열의 합

문제

14225번: 부분수열의 합

 

문제 풀이

 이 문제는 주어진 수열의 부분 합을 구하였을 때, 구할 수 없는 수를 반환하는 문제이다. 예제 입력 1에서 구할 수 있는 경우의 수를 트리로 벗는다면 위의 그림과 같다. 즉 주어진 수열을 모두 선택하는 경우와 부분적으로 선택하지 않을 때에 따라 합을 구하면 되는 것이다.

 이를 코드로 구현한다면 재귀 호출을 이용하면 쉽게 구할 수 있다. 코드를 작성하기 위해서는 다음과 같은 경우의 수를 생각하여 구현하면 된다.

 

• 중간에 발생하는 값도 기록하여야 하기에, 인덱스가 N에 이루는 경우만 값을 저장하지 않고 가지를 뻗을 때마다 부분 합을 기록한다.
• 재귀 호출을 할 때, 현재 인덱스의 값을 반영하는 것과 하지 않는 것 2가지로 나누어 재귀 호출을 한다.

 

코드

from sys import stdin


def dfs(idx, sum_num):
    global answer

    if idx == n:
        return

    answer.add(sum_num + s[idx])
    dfs(idx + 1, sum_num + s[idx])
    dfs(idx + 1, sum_num)


if __name__ == '__main__':
    n = int(stdin.readline())
    s = list(map(int, stdin.readline().split(' ')))
    answer = set(s[:])
    dfs(0, 0)

    ret = 0
    for num in range(max(answer)):
        if num + 1 not in answer:
            ret = num + 1
            break

    print(ret if ret else max(answer) + 1)

 빠진 수를 찾기 위해서는 구한 값에서 max까지의 수를 순차적으로 탐색하고 끝까지 탐색하여도 찾지 못한 경우는 max + 1 값을 반환하도록 하였다.