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

이번 글에서는 백준 14267번 문제 “회사 문화 1”을 함께 해결해 보겠습니다. 이 문제는 직원 간의 칭찬이 어떻게 전달되는지를 시뮬레이션하여 각 직원이 받은 최종 칭찬 수를 계산하는 문제입니다.

 

1. 문제 설명

1) 문제 개요

• 회사의 직원들에게 칭찬이 주어졌을 때, 그 칭찬이 상사로부터 전달되어 각 직원이 최종적으로 받은 칭찬의 수를 계산하는 문제입니다.

• 회사는 트리 구조로 구성되어 있으며, 각 직원은 하나의 상사를 가지고 있습니다.

 

2) 입력

• 첫 줄에 직원의 수 n과 칭찬 횟수 m이 주어집니다.

• 두 번째 줄에 각 직원의 상사 번호가 주어집니다. 루트 직원의 상사 번호는 -1입니다.

• 다음 m개의 줄에 걸쳐 칭찬 정보가 주어집니다. 각 줄은 두 정수 i와 w로 구성되며, i번 직원에게 w만큼의 칭찬을 한다는 의미입니다.

 

3) 출력

• 각 직원이 받은 최종 칭찬 수를 한 줄로 출력합니다.

 

2. 접근법

1) 입력받기

• sys.stdin.readline을 사용하여 입력 속도를 높입니다.

• 첫 번째 줄에서 직원의 수 n과 칭찬 횟수 m을 입력받고, 두 번째 줄에서 각 직원의 상사 번호를 입력받습니다.

 

2) 칭찬 정보 처리

• 칭찬 정보를 입력받아 각 직원이 받은 칭찬의 수를 저장하는 리스트를 생성합니다.

• 칭찬을 받은 직원의 번호는 1부터 시작하므로, 이를 0부터 시작하는 인덱스로 조정합니다.

 

3) 칭찬 전달

• 루트 직원을 제외한 나머지 직원들에 대해 상사로부터 칭찬을 전달받아 최종적으로 받은 칭찬 수를 계산합니다.

3. 정답 코드

import sys
input = sys.stdin.readline

# n: 직원의 수, m: 칭찬 횟수
n, m = map(int, input().split())
# parent: 각 직원의 상사 번호 (-1은 루트)
parent = list(map(int, input().split()))

# 상사의 번호를 0부터 시작하도록 조정
for i in range(n):
    if parent[i] != -1:
        parent[i] -= 1

# praise: 각 직원이 받은 칭찬의 수를 저장하는 리스트
praise = [0] * n

# m번의 칭찬 정보를 입력받아 처리
for _ in range(m):
    idx, cnt = map(int, input().split())
    praise[idx - 1] += cnt  # 해당 직원의 칭찬 수에 추가

# 칭찬을 전달하는 과정
# 루트 직원(0번)을 제외한 나머지 직원들에 대해 칭찬을 상사로부터 전달받음
for i in range(1, n):
    praise[i] += praise[parent[i]]

# 각 직원이 받은 최종 칭찬 수를 출력
print(*praise)

 

4. 코드 설명

1) 입력 받기

• n과 m을 입력받고, 각 직원의 상사 번호를 리스트로 입력받습니다.

• 상사 번호가 1부터 시작하므로, 이를 0부터 시작하도록 조정합니다.

 

2) 칭찬 정보 처리

• 칭찬 정보를 입력받아 해당 직원의 칭찬 수에 더합니다.

• 칭찬 받은 직원의 번호를 0부터 시작하는 인덱스로 조정합니다.

 

3) 칭찬 전달

• 루트 직원을 제외한 나머지 직원들에 대해 상사로부터 받은 칭찬을 전달받아 최종 칭찬 수를 계산합니다.

 

4) 결과 출력

• 각 직원이 받은 최종 칭찬 수를 출력합니다.

5. Github으로 확인

coTest/BOJ/BOJ01_06_05_14267.py at main · pcy4196/coTest