[ BOJ / 파이썬 ] 1182.부분수열의 합

백트래킹의 n과 m이나 n queen 문제와는 살짝 차이가 있는 풀이 유형을 익힐 수 있었다.

보통

visited[n] = 1

func(n)

visited[n] = 0 

이런 식으로 방문여부를 방문append() - 재귀 깊이 + 1 - 방문pop() 요런 느낌이었는데.

 

이 문제에서는

func( 이 단계에서 실행 X, depth+1)

func( 이 단계에서 실행 O, depth+1)

이런 식으로 풀어나갔다. 

 

...

 

그리고 해당 문제 풀이에서는 정말 기초적인 수학 이해가 필요했다.

크기가 양수인 부분수열일 때만이라는 조건을 그냥 넘기려 했는데 예제 입력처럼 합이 0인 경우 = 그러니까 크기가 0인 경우는 예외처리를 할 필요가 있었던 것이다.

놓치기 쉬운 부분이었다.

 

풀이. 정답

import sys
input = sys.stdin.readline

def recur(sum, depth):
  global result, n

  if depth == n:
    if sum == s:
      result += 1
    return
  recur(sum+series[depth], depth+1)
  recur(sum, depth+1)
      

result = 0
n, s = map(int, input().split())
series = list(map(int, input().split()))
recur(0, 0)
if s == 0:
  print(result-1)
else:
  print(result)

 

 

몇 개월 전 풀이는 위의 풀이보다 실행시간이 두 배 걸리더라.. 왜?

# 백트래킹
import sys
input = sys.stdin.readline

n, s = map(int, input().split())
array = list(map(int, input().split()))
sum = 0
count = 0

def addToSum(x, sum):
  global count
  if x >= n:
    return

  sum += array[x]
  
  if sum == s :
    count += 1
  
  addToSum(x + 1, sum)
  addToSum(x + 1, sum - array[x])
    

addToSum(0, sum)
print(count)

 

아 .. 일단 sum에 더하고, 다음 깊이로 들어가면서 그대로 두거나 / 다시 원래대로 돌리거나(*) 하는 식으로 풀어서 불필요한 리셋(*)이 일어난 것

그리고 조건이 됐을 때만 = 일정 깊이만큼 다 찼을 때만 if sum == s 로 체크하면 되는데 매번 매순간하기 때문에 걸리는 미약한 시간 소요도 있을 듯( 이건 애초에 함수가 그렇게 생겨서 어쩔 수 없이 저렇게 한 것 같음.)