[Baekjoon/🥈SilverⅡ] 1182: 부분수열의 합

Intro

Algoritm👩‍💻: combination

#21.01.12
#1182: 부분수열의 합

import sys, itertools
N, S = map(int, sys.stdin.readline().rstrip().split())
lst = list(map(int, sys.stdin.readline().rstrip().split()))
count = 0

for i in range(1, N+1):
  result = list(itertools.combinations(lst, i))
  for j in result:
    if sum(j) == S:
      count += 1

print(count)

• 주어진 수열로 만들 수 있는 모든 부분수열을 구한다.
  • combination 함수 사용!
• 부분수열의 합이 S인 경우를 카운트한다.

Algoritm👩‍💻: DFS

import sys

def dfs(index, sum):
  global count
  if index >= N:
    return
  sum += lst[index]
  if sum == S:
    count += 1
  dfs(index + 1, sum)
  dfs(index + 1, sum - lst[index])

N, S = map(int, sys.stdin.readline().rstrip().split())
lst = list(map(int, sys.stdin.readline().rstrip().split()))
count = 0
dfs(0, 0)
print(count)

• 인덱스를 하나씩 늘려가며 순열의 모든 값을 순회한다.
  • 해당값을 더했을 경우와 더하지 않았을 경우로 나누어 재귀함수를 구현한다.
    • dfs 적용!

참고📃

• https://pacific-ocean.tistory.com/306

이번 포스팅은 여기서!!

끝!! ~(˘▾˘~)