[모각코] 210728 Today I Learned

<백준 1949번 - 우수 마을>

 

골드1... 함부로 건드리면 안된다... 진짜...

 

문제부터 잘 이해가 안 돼서 계속 읽었다. 겨우겨우 이해한 바는

• 각 노드에서 나아갈 수 있는 방향은 '우수마을' or 'not 우수마을' 이렇게 두 가지 경우.
• 루트 노드가 우수 마을이면 하위 노드는 우수 마을 일 수 없다.
• 루트 노드가 우수 마을이 아니면, 하위 노드는 우수 마을이거나 아니거나. (둘 중 최댓값....아마도)

 

이걸 dp에 저장하는 게 역시나 난관이었는데

dp[i][0] : 현재(i) 마을이 우수 마을이 아닌 경우

dp[i][1] : 현재(i) 마을이 우수 마을인 경우

로 저장했다.

 

제출했는데 recursion error 떠서 절망적이었다.. 근데 recursionlimit 풀어주니까 바로 됐다.

사실.. 어떻게 이렇게 빨리 풀 수 있었는지 잘 모르겠다.

모각코 하는 두 시간 동안 한 문제 풀기 정말 쉽지 않은데... 어쨌든 맞았으니까 넘어간다 ~!

 

 

 

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def village(start):
    if visited[start]:
        return
    visited[start] = True

    for i in tree[start]:
        if not visited[i]:
            village(i)
            dp[start][0] += max(dp[i][0], dp[i][1])
            dp[start][1] += dp[i][0]
    
n = int(input())
people = [0] + list(map(int, input().split()))
tree = [[] for i in range(n+1)]
visited = [0 for i in range(n+1)]
dp = [[0, people[i]] for i in range(n+1)] #[i][0]: 우수마을 x, [i][1]: 우수마을
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
village(1)
print(max(dp[1][0], dp[1][1]))