[백준 14267] 회사 문화1 (python)

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

14267번: 회사 문화 1

회사 문화1 문제

상사로부터 부하로 칭찬을 내리 칭찬할 경우 받는 칭찬의 수를 구하는 문제

 

#사용 알고리즘

다이나믹 프로그래밍

📌문제 접근 포인트

1. 상사가 받는 칭찬은 본인 보다 부하인 직급에 모두 더해진다. 그러므로 받은 칭찬을 우선적으로 구하고, 해당 상사의 부하들에 대해 칭찬 수를 증가해주면 된다.

2. 칭찬 포인트(good)를 만들어서 각 상사에 매칭되는 최초 칭찬 값을 넣어주자.

3. 이제 각 상사의 부하직원들에게 칭찬 포인트를 더해주면 되는데, 이때 기본적으로 직속상사 번호가 더 작다는 전제 조건이 있으므로 보스를 제외한 나머지 상사들을 기준으로 앞에서부터 for문을 이용하여 해당 번호(상사)의 부하가 갖는 칭찬 수만큼 더해지므로, 쉽게 DP를 이용하여 구할 수 있었다.

⚙ 내가 푼 정답 코드

import sys
n, m = map(int, sys.stdin.readline().split())
grade = [0] + list(map(int, sys.stdin.readline().split()))
good = [0]*(n+1)

for _ in range(m):
    s,p = map(int, sys.stdin.readline().split())
    good[s] += p

for i in range(2, n+1):
    good[i] += good[grade[i]]

print(*good[1:])