백준 1182 부분수열의 합

처음엔 그냥 단수한 조합문제라고 생각하고 풀었는데
약간의 함정이 있었다..
목표로하는 값이 0인 경우와 음수인 경우를 생각해야 했다.

📜 문제 바로 가기 : 부분수열의 합

제출코드

import sys
input = sys.stdin.readline

N, S = map(int, input().split())
arr = list(map(int, input().split()))

# arr.sort()

def recur(s, k, flag):
    global ans

    if k == S and flag:
        ans += 1
    
    if s == N:
        return
    
    # if k > S:
    #     return

    recur(s+1, k, False)
    recur(s+1, k+arr[s], True)

    
ans = 0
recur(0, 0, False)
print(ans)

---

접근방법

재귀를 이용한 단순 조합코드이다.
단, 위에서 말한 경우를 생각해줘야한다.
k 값이 0 부터 시작하기때문에 목표값이 0 인경우 아무것도 더하지 않았음에도 통과되는 경우가 있다. 그래서 flag 변수를 뒀다. 아무것도 더하지 않는다면 이를 False 로 둠으로서 목표값과 같더라도 카운팅하지 않는다.

정렬에 대해서

처음에 '정렬을 시키고 하나씩 더해보자, 그리고 k 가 목표값보다 커진다면 정렬되있기 때문에 그 뒤는 볼 필요가 없을거야' 라고 생각했고 이는 잘못된 생각이었다.
수열의 값이 음수도 들어오기 때문에 이부분을 생각해야한다.
예를 들어 목표하는 값이 음수인경우 음수는 더 할수록 작아지기 때문에 목표로하는 음수값을 위해서는 현재값이 더 커도 다음에 더할 값이 음수라면 고려대상이 된다.

즉, 정렬을 한다고하면 주석 부분을 아래와 같이 고치면 된다.

if k > S and arr[s] >= 0:
    return