[백준][DP][배낭문제] 할로윈의 양아치

할로윈의 양아치

 

• 내 풀이
  • BFS+ Bottom-Up방식 
  • (그룹 인원 수, 총 캔디 수) 로 그룹 만들기
  • dp[i]를 i명 까지의 최대 캔디 수라고 생각하고 코드 짜려 했지만 안 짜짐
    • → 2차원 dp 써야하는데 생각을 못했다.
  • DP = 배낭문제
    • dp[그룹 번호][i명 까지의 최대 캔디 수] 가 되도록 dp 생성
    • dp[i][j]는 i번째 그룹까지 고려했을 때, j명의 아이를 선택했을 때 얻을 수 있는 최대 사탕 개수  
      • 현재 그룹 선택 안하는 경우: 이전 그룹까지 중 i명
      • 현재 그룹 선택 하는 경우: 이전 그룹에서 i-(현재 그룹인원)명 + 현재 그룹

from collections import deque


n, m, k = map(int, input().strip().split())
candy = [0] + list(map(int, input().strip().split()))

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().strip().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [False] * (n + 1)

def bfs(start):
    queue = deque()
    queue.append(start)
    visited[start] = True

    members = 1
    total = candy[start]

    while queue:
        x = queue.popleft()

        for nxt in graph[x]:
            if not visited[nxt]:
                visited[nxt] = True
                queue.append(nxt)
                members+=1
                total += candy[nxt]

    groups.append((members, total))

groups = []
for i in range(1, n + 1):
    if not visited[i]:
        bfs(i)

dp = [[0 for _ in range(k)] for _ in range(len(groups) + 1)]

for i in range(1, len(groups) + 1):
    members, total = groups[i - 1]

    # i 번째 그룹까지만 있다고 생각했을 때, j명 까지의 최대 사탕 갯수
    for j in range(1, k):
        if j < members:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - members] + total)

print(dp[len(groups)][k-1])

 

• 다른 사람 풀이
  • union-find + Top-down방식
  • dp[j]: 아이를 j명 선택했을 때 얻을 수 있는 최대 사탕 개수
  • dp[j - group_size[i]] + group_candy[i]
    • j - group_size[i]만큼 선택하고 현재 그룹을 더할 때 얻을 수 있는 최대 사탕 개수

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

# 유니온-파인드 (Find)
def find(x):  
    if parent[x] != x:  
        parent[x] = find(parent[x])  
    return parent[x]  

# 유니온-파인드 (Union)
def union(x, y):  
    # 각 값의 최상위 루트 찾기
    x, y = find(x), find(y)

    # 더 작은 루트 노드에 합친다 (최소 힙 구조 유지)
    if x < y:
        parent[y] = x
    else:
        parent[x] = y  

# 배낭 문제 풀이
def knapsack():  
    for i in range(1, n + 1):  
        if i != parent[i]:  
            continue  
        for j in range(k - 1, group_size[i] - 1, -1):  
            dp[j] = max(dp[j], dp[j - group_size[i]] + group_candy[i])  

# 입력 받기
n, m, k = map(int, input().split())  
candy = [0] + list(map(int, input().split()))  
parent = [i for i in range(n + 1)]  
group_size = [1] * (n + 1)  

# 친구 관계 입력
for _ in range(m):  
    a, b = map(int, input().split())  
    union(a, b)  

# 친구 그룹별 사탕 개수 & 크기 업데이트
group_candy = candy[:]
for i in range(1, n + 1):  
    if i != parent[i]:  
        root = find(i)  
        group_candy[root] += candy[i]  
        group_size[root] += group_size[i]  

# 배낭 문제 풀이 (DP)
dp = [0] * k  
knapsack()  
print(max(dp))