☂️ 엘리스 코드 챌린지 ☂️ - 4회차

느지막히 저녁에 하게 된..

---

☂️ 4회차

들리는 소문들을 보아하니..

오늘은 쉽지 않나?

그리디패배

젠장

예제 두개가 맞는 것 같길래 했더니 예제만 맞게 하다니...

트리 DP + dfs 

패배...뭐지

아오

와ㅋㅋㅋㅋㅋㅋ2분 남기고ㅋㅋㅋㅋ성공했다

import sys

def dfs(node, parent):
    if (len(tree[node]) == 1 and tree[node][0] == parent):
        dp[node] = node
        return node

    max_gain = sys.minsize()
    for child in tree[node]:
        if child != parent:
            child_gain = dfs(child, node)
            max_gain = max(max_gain, node-child_gain)
    
    dp[node] = max_gain
    return dp[node]

N = int(sys.stdin.readline())
tree = [[] for _ in range(N+1)]
dp = [0] * (N + 1)
    
for _ in range(N-1):
    u,v = map(int,sys.stdin.readline().split())
    tree[u].append(v)
    tree[v].append(u)
    
dfs(1, -1)
    
result = []
for i in range(1, N + 1):
    if dp[i] >= 0:
        result.append(1)  
    else:
        result.append(0)  


for cha in result:
    print(cha)

dp[] 배열 : 각 노드에서 게임을 시작했을 때, 최적의 전략을 사용했을 때의 "점수 차이"

 dp[node]가 양수라면 => 선공이 유리

음수라면 => 후공이 유리

 

max_gain = max(max_gain, node - child_gain) 이렇게 하면 됨!!

이걸 굳이 매 턴마다 선공점수 후공점수 계산할 필요 없고 리프에서부터 올라오면서 차이를 계속 계산하면 됨!!

---

그치 문제 좀 어렵다고

온니들

오랜만에 알고리즘고수신촌판 난입