[백준] 1182번: 부분수열의 합 - Python (Re)

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

 

 

 

아이디어

• 모든 경우의 수를 탐색하는 문제이므로 백트래킹을 활용한다.
• back 함수는 인자로 idx와 li_sum을 받는다.
  • idx는 현재 탐색할 수열의 인덱스를 의미하며, 이를 통해 a + b 와 b + a 같이 중복되는 조합을 방지할 수 있다.
  • li_sum은 지금까지 선택한 수들의 합이며, 이 값을 s와 비교해 조건을 만족하는지 판단한다.
• 현재 합이 s와 같으면 cnt를 1 증가시킨다.
• 하지만 여기서 탐색을 멈추는 것이 아니라 이후 값을 더한 경우도 여전히 조건을 만족할 수 있으므로 재귀를 이어간다.
• 다만 s == 0인 경우 아무 값도 선택하지 않은상태에서 li_sum == s가 성립하므로 마지막에 cnt에서 1을 빼준다.

구현

import sys
input = sys.stdin.readline

def back(idx, li_sum):
    global cnt
    if li_sum == s:
        cnt +=1
    for i in range(idx, n):
        li_sum += li[i]
        back(i+1, li_sum)
        li_sum -= li[i]

n, s = map(int, input().split())
li =  list(map(int, input().split()))
cnt = 0
li_sum = 0
back(0, li_sum)

if s == 0:
    cnt -=1

print(cnt)

 

마무리

어렵지 않은 문제였지만 아무 생각없이 li_sum == s에 걸리면 return으로 함수를 끝내버리도록 코드를 작성했었다.

단순히 조건을 만족한다고 해서 탐색을 멈추면 이후 가능한 경우들을 놓칠 수 있다는 점을 주의하자.