할로윈의 양아치 ( 20303 번 )

20303번: 할로윈의 양아치

 

---

🧠 알고리즘

• 유니온 파인드 + 배낭 문제(Dynamic Programming)

 

✔️ 동작 방식

• 그룹 묶기 (Union-Find)
• 각 그룹의 총 인원 수(group_count)와 총 사탕 수(candy)를 합산.
• DP로 최대 사탕 수 계산 (배낭 문제 방식)
• 결과 출력 > max(dp)

---

 

🧾 코드

import sys

def _find_pt(num, pt_list):
    if num != pt_list[num]:
        pt_list[num] = _find_pt(pt_list[num], pt_list)
    return pt_list[num]


def _union(x, y, pt_list):
    x_root, y_root = _find_pt(x, pt_list), _find_pt(y, pt_list)
    if x_root > y_root:
        pt_list[x_root] = y_root
    else:
        pt_list[y_root] = x_root


def _main(n, m, k, candy):
    """
        1. 그룹 인원 + 해당 그룹 사탕 수 구하기
        2. dp로 k 미만의 최대 사탕 수 구하기!!
    """
    pt_list = [i for i in range(n + 1)]
    group_count = [0] * n
    dp = [0] * k
    
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().rstrip().split())
        a_root, b_root = _find_pt(a, pt_list), _find_pt(b, pt_list)
        _union(a_root, b_root, pt_list)

    for idx in range(1, n + 1):
        now_root = _find_pt(idx, pt_list)
        
        if idx != now_root:
            candy[now_root - 1] += candy[idx - 1]
        group_count[now_root - 1] += 1
    
    for idx in range(n):
        if group_count[idx] > 0:
            gp_count, total_candy = group_count[idx], candy[idx]
            for j in range(k - 1, gp_count - 1, -1):
                dp[j] = max(dp[j], dp[j - gp_count] + total_candy)

    return max(dp)
    

n, m, k = map(int, sys.stdin.readline().rstrip().split())
candy = list(map(int, sys.stdin.readline().rstrip().split()))
print(_main(n, m, k, candy))

---

 

⏱️ 시간 복잡도

for idx in range(n) : 그룹 수 만큼 순회 ( 선형 시간 복잡도 )
	if group_count[idx] > 0:
		gp_count, total_candy = group_count[idx], candy[idx]
		for j in range(k - 1, gp_count - 1, -1) : 최소 인원 만큼 순회 ( 선형 시간 복잡도 )
        
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )