1182 부분수열의 합

💡문제 분석 요약

• n개의 정수와, 목표합 s를 받아서 부분 수열의 합이 s가 되는 경우의 수를 구한다.

💡알고리즘 설계

• DFS를 쓰지 않아도 풀 수 있어보인다. N의 개수도 20으로 그리 크지 않아서 for문으로 모든 경우를 다 구해도 되지 않을까 생각이 들었다.
• combination을 이용하여 1개, 2개, 3개 ..... n개를 뽑는 경우를 모두 구한 후, sum이 s와 같은지 비교하여 개수를 구한다.

💡코드

import sys
from itertools import combinations as cb
input = sys.stdin.readline

n, s = map(int, input().split())
lst = list(map(int, input().split()))

# 부분 수열의 합이 s가 되는 개수를 구함
cnt = 0
for i in range(1, n+1): # 처음에 n으로 했어서 틀림
    tmp = cb(lst, i) # i개 뽑은 조합들이 쭉 들어가있음
    for j in tmp:
        if sum(j) == s:
            cnt += 1
print(cnt)

""" Test Case 주의사항
1. 비어있거나, 하나만 있는 case
2. 첫번째 혹은 맨 마지막 case
3. 크기가 굉장히 큰 case
4. 양수만 있는, 음수만 있는 case
5. overflow가 나는 case
6. 중복 값이 들어가는 case
"""

💡시간복잡도

• combination 자체가 2^n으로 꽤 적지 않은 시간인데, n개의 수에 대해서 모두 진행하므로 O(n * 2^n)만큼 걸릴 것이다.

💡 틀린 이유

• n개를 뽑는 경우까지 가야하는데 for문을 range(n)까지로 했어서 n-1개 뽑는 경우까지 가서 37%에서 계속 틀렸다.

💡 틀린 부분 수정 or 다른 풀이

• for문 n-1로 수정
• 백트래킹 파트이므로, 백트래킹으로도 풀 수 있어야한다.
• sum( [ ] ) 이것도 0으로 찍히므로, len(tmp)가 0보다 커야한다는 조건이 필요하다.

N, S = map(int, input().split())
arr = list(map(int, input().split()))
tmp = []
cnt = 0

def backTracking(start):
    global cnt
    if sum(tmp) == S and len(tmp) > 0:
        cnt += 1

    for i in range(start, len(arr)):
        tmp.append(arr[i])
        backTracking(i + 1)
        tmp.pop()  # 다음 단계로 넘어갈떄

backTracking(0)
print(cnt)

💡 느낀점 or 기억할정보

• 쉬워보이는 문제여도, 결국 edge case를 찾지 못하면 디버깅하는데에 시간이 오래 걸린다.