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

문제 링크

---

https://www.acmicpc.net/problem/1182

풀이 코드

---

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

cnt = 0
dap = []

def hap(inp):
    global cnt
    if sum(dap) == s and dap:
        cnt += 1
    for i in range(inp, n):
        dap.append(num[i])
        hap(i+1)
        dap.pop()

hap(0)
print(cnt)

코드 해석

---

재귀함수를 사용한다.

dap이라는 빈 리스트를 만든 뒤 

리스트에 숫자들을 넣는다.

만약 리스트의 합이 s와 같다면 cnt + 1을 한다.

 

n = 5, s = 0, num = [-7,-3,-2,5,8] 이라면 dap은 다음과 같다.

[-7]
[-7, -3]
[-7, -3, -2]
[-7, -3, -2, 5]
[-7, -3, -2, 5, 8]
[-7, -3, -2, 8]
[-7, -3, 5]
[-7, -3, 5, 8]
[-7, -3, 8]
[-7, -2]
[-7, -2, 5]
[-7, -2, 5, 8]
[-7, -2, 8]
[-7, 5]
[-7, 5, 8]
[-7, 8]
[-3]
[-3, -2]
[-3, -2, 5]
[-3, -2, 5, 8]
[-3, -2, 8]
[-3, 5]
[-3, 5, 8]
[-3, 8]
[-2]
[-2, 5]
[-2, 5, 8]
[-2, 8]
[5]
[5, 8]
[8]

 

 

체감 난이도: ★★★★☆

이해가 어려워서 해석 보고 풀었다..