문제 바로가기
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
나의 코드 및 설명 - 멀티 트리
- 현재 방문한 수열의 인덱스에 대해 v 리스트를 활용하여 방문 처리를 해주었고, 합의 개수를 셀 때 중복된 값을 세지 않도록 for문의 시작점을 dfs의 변수에 넘겨주었다.
def dfs(count, temp_sum, start):
global ans
if temp_sum >= k:
if temp_sum == k:
ans += 1
return
if count == n:
return
for i in range(start, n):
if v[i] == 0:
v[i] = 1
dfs(count + 1, temp_sum+num_list[i], i+1)
v[i] = 0
t = int(input())
for test_case in range(1, t+1):
n,k = map(int, input().split())
num_list = list(map(int, input().split()))
num_list.sort()
ans = 0
v = [0] * (n)
dfs(0,0,0)
print(ans)
다른 코드 및 설명 - 이진 트리
def dfs(index, temp_sum):
global ans
if temp_sum > k:
return
if temp_sum == k:
ans += 1
return
if index == n:
return
dfs(index+1, temp_sum)
dfs(index+1, temp_sum+num_list[index])
t = int(input())
for test_case in range(1, t+1):
n,k = map(int, input().split())
num_list = list(map(int, input().split()))
num_list.sort()
ans = 0
v = [0] * (n)
dfs(0, 0)
print("#{} {}".format(test_case, ans))
'SWEA (SW Expert Academy) > D3' 카테고리의 다른 글
[SWEA/D3] 2814 최장 경로 / DFS (0) | 2023.04.25 |
---|---|
[SWEA/D3] 1216 회문2 / 2차원 리스트 가로,세로 변환 (0) | 2023.04.25 |
[SWEA/D3] 5215 햄버거 다이어트 / 백트래킹 (0) | 2023.04.13 |
[SWEA/D3] 1206 [S/W 문제해결 기본] 1일차 - View (0) | 2023.04.10 |
[SWEA/D3] 13547 팔씨름 (0) | 2023.03.26 |