💡 문제
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
출력
첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.
💭 접근
이 문제는 입력의 최대가 20이기 때문에 최악의 경우 1~20 까지의 모든 조합을 만들어야한다. 이렇게하면 시간초과로 인해 틀리게 되는데, 11723번 집합 문제와 같이 그 수가 포함되어 있는 여부를 0 or 1로 나타내어 해결해야한다.
즉, True와 False로 이루어진 n개의 중복 순열을 만들어 True에 해당하는 index에 있는 수들만 더하여 s와 비교해주면 된다.
ex) 예제, n = 5, s = 0, arr = [-7, -3, -2, 5, 8]
ex 1. mask = [F, T, T, T, F] -> [-7, -3, -2, 5, 8] -> (-3) + (-2) + 5 = 0 (정답)
ex 2. mask = [T, T, T, F, F] -> [-7, -3, -2, 5, 8] -> (-7) + (-3) + (-2) = -12 (오답)
여기서 한가지 주의해야할 점은 mask의 모든 원소가 False가 될 때인데, 이때는 원소가 하나도 포함되지 않은 것이므로 문제에서 주어진 크기가 양수인 부분수열이라는 조건에 맞지 않는다. 그러나 s가 0이 아닐때는 정답이 아니기에 신경쓸 부분이 아니지만, s가 0일 때는 출력해야하는 값보다 +1 큰 수가 출력되므로 마지막에 신경을 써주어야 한다.
print(ans - 1 if ans != 0 and s == 0 else ans)📒 코드
def dfs(depth):
global ans
if depth == n:
sum = 0
for i in range(n):
if mask[i]:
sum += arr[i]
if sum == s:
ans += 1
return
for tf in flag:
mask.append(i)
dfs(depth + 1)
mask.pop()
n, s = map(int, input().split())
arr = list(map(int, input().split()))
flag = [False, True]
mask = []
ans = 0
dfs(0)
print(ans - 1 if ans != 0 and s == 0 else ans)💭 후기
11723번 집합 문제와 비슷한 개념을 사용하여 어렵지 않게 해결할 수 있었다.
🔗 문제 출처
https://www.acmicpc.net/problem/1182
