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

 

🔒 문제

14267번: 회사 문화 1

 

 

🔑 알고리즘

트리, 그래프, DP

 

 

 

💡  풀이

먼저 문제의 입력이 애매하게 설명되어있는데

한 명의 부하는 한 명의 직속 상사만 가질 수 있지만

한 명의 상사는 여러 명의 직속 부하를 가질 수 있는 트리 구조이다.

 

출력할 때 1번부터 n번의 직원의 칭찬을 출력하므로, 즉 상사부터 부하 순으로 출력하므로

1번부터 n번의 직원까지,

[자신의 직속 상사가 받은 칭찬의 정도]와 [자신이 직속 상사로부터 받은 칭찬의 정도(입력 값)]를 더해 출력하고 저장하고 있으면 된다.

그러면 자연스레 다시 자신의 직속 부하의 출력 순서가 됐을 때 자신이 가진 칭찬의 정도를 탐색하는 구조가 된다.

 

자신의 상사 번호를 저장하는 배열과

자신이 받은 칭찬 값을 저장하는 배열 두가지만 사용하면 되는 문제이다.

 

* 사장의 상사가 -1로 입력되므로 사장의 상사를 찾을 때 배열의 인덱스로 -1이 들어가게 된다.

따라서 사장의 상사 인덱스의 값을 -1에서 0으로 고쳐준다.

 

 

✏️ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int[] bossIndex = new int[n + 1];
		int[] arr = new int[n + 1];

		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 1; i <= n; i++) {
			bossIndex[i] = Integer.parseInt(st.nextToken());
		}
		bossIndex[1] = 0;

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int index = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());

			arr[index] += w;
		}

		for (int i = 1; i <= n; i++) {
			arr[i] += arr[bossIndex[i]];
			System.out.print(arr[i] + " ");
		}
	}
}