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

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

1182번: 부분수열의 합

아이디어

• 백트래킹으로 요소를 선택하며 합한 수를 tmp에 저장
• tmp가 s와 같아지면 cnt + 1
• 백트래킹 함수의 인자로 현재 더한 요소 인덱스+1로 넘겨주어 그다음 요소부터 선택하게 설계

구현

import sys
input = sys.stdin.readline

def back(idx):
    global tmp, cnt
    if tmp == s:
        cnt += 1

    for i in range(idx, n):
        tmp += li[i]
        back(i+1)
        tmp -= li[i]

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

li = list(map(int, input().split()))

tmp = 0
cnt = 0
back(0)

if s == 0:
    print(cnt-1)
else:
    print(cnt)

이게 한번 틀렸다가 맞앗는데

그 이유가 처음에는 if tmp == s에 return을 넣어주어서 그렇다

 

return을 넣어주면 문제가 s가 0이면 백트래킹 함수가 실행됨과 동시에 종료가 된다.

또한 tmp가 s와 같아지고 또 그다음에 -1을 하고 +1을 해주면 또 tmp == s인 경우가 있기 때문에 return으로 탐색을 끝내면 안 된다.

그래서 s가 0이면 가장 처음 if문에 걸려 더해지는 1을 빼주어야 했다.

 

마무리

• 단순 백트래킹 형식을 무의식적으로 구현하다 틀렸던 문제
• 브루트포스와 백트래킹 두 가지 성향을 가졌던 문제였다.