[SWEA] 파이썬 2817. 부분 수열의 합 | BFS

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV7IzvG6EksDFAXB&categoryId=AV7IzvG6EksDFAXB&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=PYTHON&select-1=3&pageSize=10&pageIndex=1 

SW Expert Academy

 

 

문제 해결 포인트

- BFS를 이용하여 각 숫자를 더한 경우, 더하지 않은 경우를 모두 방문

- 모든 숫자를 돌았을 때 찾던 값이라면 해당 경우 카운트

 

 

- 프로그래머스 '타겟 넘버'와 해결 포인트가 유사하므로 참고하세요

2023.04.19 - [📁문제 풀이/🧩Programmers] - [Python] 프로그래머스 타겟 넘버 | DFS/BFS

 

 

작성 코드

from collections import deque

for test in range(1, int(input())+1):
    result = 0
    que = deque()
    N, K = list(map(int, input().split()))
    numbers = list(map(int, input().split()))

    que.append((1, numbers[0]))
    que.append((1, 0))
    while que:
        q = que.popleft()
        if q[0] == N:
            if q[1] == K:
                result += 1
        else:
            que.append((q[0]+1, q[1] + numbers[q[0]]))
            que.append((q[0]+1, q[1]))

    print('#{} {}'.format(test, result))

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚