[백준 - Python] 14267 - 회사 문화 1

0.  문제 링크

 

 

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

14267번: 회사 문화 1

---

1.  풀이 방법

 

 

 

1번 시도(트리라 생각함)
1. defaultDict을 이용해서 자신의 직속 후임을 리스트로 만들어놓음
2. 그리고 우선 자신에게 칭찬을 더하고, 후임들을 또 재귀함
3. 재귀 제한에 걸려서, 다시 수정하고 제출하니 이번엔 시간 초과

2번 시도(트리에 BFS를 적용함)
1. 재귀 때문에 시간 초과라 생각함
2. 그래서 재귀를 bfs로 변경해서 구현함
3. 시간 초과

3번 시도(트리에 DP를 적용함), 정답
1. 굳이 일일이 다 더해야 되나 생각함
2. 곰곰히 생각해 보니까 dp처럼 직속 상사의 칭찬에 나의 칭찬을 더하면 되는 거였음
3. 결론적으로 출력 시에 직속 상사의 칭찬에 나의 칭찬을 더해서 저장하고, 그것을 출력함
4. 리스트를 계속 들고 있는 이유는 99,999번째의 직속 상사가 1번일 수도 있기 때문

---

2.  코드

 

 

import sys
input = sys.stdin.readline
print = sys.stdout.write


def sol():
    n, m = map(int, input().split())
    maps = [0] + list(map(int, input().split()))

    good_stamp = [0] * (n + 1)

    for _ in range(m):
        i, w = map(int, input().split())
        good_stamp[i] += w      # 자신의 칭찬 스티커를 추가함

    print('0 ')
    for i in range(2, n + 1):
        good_stamp[i] += good_stamp[maps[i]]        # 직속 상사의 칭찬 스티커에 자신의 칭찬 스티커를 더함
        print("%d " % good_stamp[i])


sol()

---

3.  마무리

 

 

파이썬 1등 나이스