[Python/파이썬] 백준 14267번 회사 문화 1

https://www.acmicpc.net/problem/14267

코드

import sys
input = sys.stdin.readline

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

compliments = [0]*(n+1)
for _ in range(m):
    i, w = map(int, input().split())
    compliments[i] += w

for i in range(2, n+1):
    compliments[i] += compliments[boss[i]]

print(*compliments[1:])

 

해당 문제는 트리디피 알고리즘으로 풀 수 있는 문제에 속하긴 하지만, 문제의 조건이 쉬워서 DP만으로도 풀 수 있었다.

 

문제를 보면 직속 상사의 번호가 자신의 번호보다 작다고 되어 있다. 그렇기 때문에 DFS를 이용해서 트리를 탐색할 필요 없이 for문만으로도 트리를 다 탐색하며 각 직원이 칭찬 받은 정도를 구할 수 있었다. 자신의 직속 상사가 칭찬을 받은 정도에 자신이 받은 칭찬만 더하면 되니까 쉽다.