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

문제 보러 가기

N개 정수로 이뤄진 수열이 있다. 크기가 양수인 부분 수열(원소가 1개 이상인 부분 수열이라는 뜻 같다) 중에서 원소들을 다 더한 값이 S가 되는 경우의 수 구하기!!

dfs에서 몇번째 인덱스를 볼건지(depth), 그때까지 부분 수열에 포함한 원소의 인덱스들(history), 그때까지 부분 수열 원소들의 합(total)을 가지고 다녔다.
크기가 양수이고(=history가 빈 문자열이 아니고), 그 수열 원소를 다 더한 값이 S면 그때까지의 history(몇 번 몇 번 인덱스를 포함했는지)를 set에 넣어줬다.
depth번째 수를 포함하는 부분 수열을 만드는 경우, 포함하지 않는 부분 수열을 만드는 경우를 따져주었다.

처음에는 런타임에러(RecursionError)가 떴다..ㅠㅠ N이 최대 20이니까, 최대 재귀 깊이를 2^20+1로 바꿔주었다.

그리고도 계속 틀렸습니다가 떴다. 그 이유는 total이 S가 되었을 때, 그 부분 수열을 set에 저장한 후에 return을 했기 때문이었다. 그러면 안되는 것이었다!! 만약 N이 4, S가 0이고 arr에 -1, 1, 10, -10이 있다면, 부분 수열 중 원소들을 더한 값이 S가 되는 경우의 수는 3가지이다. (-1, 1 & 10, -10 & -1,1,-10,10) 그런데 return을 해버리면 -1,1,-10,10과 같은 경우(부분 수열 원소들의 합이 S를 만족했다가, 그 부분 수열에 또 다른 수들이 포함되어서 새로운 부분 수열이 되었는데 그때도 S를 만족하는 경우)는 세지 못하게 된다.

import sys

input = sys.stdin.readline
sys.setrecursionlimit(2 ** 20 + 1)
MIIS = lambda: map(int, input().split())

N, S = MIIS()
arr = list(MIIS())
ans = set()
cnt = 0

def dfs(depth: int, history: str, total: int):
    global cnt

    if history:  # 크기가 양수인 부분 수열이고
        if total == S:  # 그 수열의 원소를 다 더한 값이 S가 되었으면
            ans.add(history)
            # 여기에서 리턴을 해서 틀렸다..ㅠㅠ

    if depth == N:
        return

    dfs(depth + 1, history + str(depth) + '-', total + arr[depth])  # 포함
    dfs(depth + 1, history, total)  # 포함 X

dfs(0, '', 0)
print(len(ans))

다른 방법

import sys

input = sys.stdin.readline
sys.setrecursionlimit(2 ** 20 + 1)
MIIS = lambda: map(int, input().split())

N, S = MIIS()
arr = list(MIIS())

cnt = 0


def dfs(depth: int, history: bool, total: int):
    global cnt

    if depth == N:  # 끝까지 다 봤고
        if history and total == S:  # 크기가 양수이고, 그 수열의 원소를 다 더한 값이 S가 되었으면
            cnt += 1
        return

    dfs(depth + 1, True, total + arr[depth])  # 포함
    dfs(depth + 1, history, total)  # 포함 X


dfs(0, False, 0)
print(cnt)

history로, 그때까지의 수열 원소를 다 들고 다닐 필요는 없다 !!