백준 #1182 부분수열의 합

코드

import sys
sys.stdin = open("input.txt")

def solve(cnt, interval_sum):
    global answer

    if cnt == n:
        if interval_sum == s:
            answer += 1
        return

    solve(cnt + 1, interval_sum + arr[cnt]) # 현재 위치의 숫자를 포함
    solve(cnt + 1, interval_sum)            # 현재 위치의 숫자를 안 포함

n, s = map(int, input().split())
arr = list(map(int, input().split()))
answer = 0
solve(0, 0) # 현재 index, 합

if s == 0:
    answer -= 1

print(answer)

풀이

어제에 이어 골드 수준의 백트래킹 문제를 도전하던도중 뭔가 많이 잘못되고 헤매는 느낌을 받아서

기본적인 백트래킹 문제들을 하나씩 풀어보고 있다. 그 중에 제일 정석적인 것 같은 문제를 포스팅 했다.

백트래킹은 DFS와 접목되어 있기 때문에 헷갈리는 부분이 아직도 많다. 더 열심히 풀어야 겠다는 생각을 했다.

또한 오늘 문제들을 풀면서 나의 코드에 주석들이 사라져 가고 있다는 사실을 발견했다.

티어는 플레티넘인데 실버 골드 문제에서 헤매고 있다니…다시 기본으로 돌아가서 차근차근 올라가보자!