백준 14267번 회사 문화1 (C++)

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

14267번: 회사 문화 1

 

문제조건

- 각 노드들은 부하를 자식으로 갖는다. 그리고 각 노드가 칭찬을 받으면 부하에게 전달되는 식으로 코드를 전개하면 된다.

 

내 접근

- 그래서 한 직원이 칭찬을 받으면 내리칭찬으로 dfs를 하고 칭찬을 받으면 dfs하는 식으로 구성했다. 그러나 이것은 dfs를 계속 반복하게 되어 좋지 않은 풀이가 된다. 그래서 시간초과에 걸렸다.

 

올바른 접근법

- 올바른 접근법은 칭찬을 받고 이전의 정보를 가지고 있는 채로 부하들을 칭찬하며 자신의 칭찬 포인트가 부하에게 전달되는 것이다.

각 노드가 칭찬을 받은 정보를 배열에 담아두고 dfs를 한번에 돌며 칭찬포인트를 갱신하는 것이다. 

 

1. 사원이 자신의 부하를 자식으로 갖도록 트리 구성

2. 칭찬 정보를 배열에 저장

3. dfs(n, value) n번 사원이 칭찬을 받으면 정답칭찬배열[n] = 정답칭찬배열[n] + 개인칭찬배열[n] + value 여기서 value는 선배로부터 오는 내리칭찬이고 개인칭찬배열은 자신이 직접 칭찬을 받은 것임.

 

그러므로, 만약 2번이 3,4번의 직속상사일 때, 2번이 3의 칭찬을, 4번이 5의 칭찬을 받았다면

dfs(2, 0)

정답칭찬배열[2] += 개인칭찬배열[2](3) + 내리칭찬(0) = 2

dfs(3, 2)

정답칭찬배열[3] += 개인칭찬배열[3](0) + 내리칭찬(2) = 2

dfs(4,2)

정답칭찬배열[4] += 개인칭찬배열[4](5) + 내리칭찬(2) = 7

 

이런식으로 돌아간다. 트리에서의 DP 태그가 붙어있는 것도 이것 때문이다.

 

이렇게 조건을 줄 때, dfs를 여러번 하게 된다면 의심해보고 최대한 dfs 순회는 작게 설정하자. 또, 메모이제이션 습관을 들이자.

 

	#include<iostream>
	#include<vector>
	#include<queue>
	#define MAX 100001
	using namespace std;

	int N, M;

	vector<int> staff[MAX];
	int thank[MAX];
	int Array[MAX];

	void dfs(int num, int value) {
		thank[num] += Array[num] + value;
		if (staff[num].size() == 0)
			return;
		for (int i = 0; i < staff[num].size(); i++) {
			dfs(staff[num][i], thank[num]);
		}
	}

	int main() {
		ios_base::sync_with_stdio(NULL);
		cin.tie(NULL);

		cin >> N >> M;

		for (int i = 0; i < N; i++) {
			int boss;
			cin >> boss;

			if (boss == -1) { 
				thank[i + 1] = 0;
				continue;
			}		
			thank[i + 1] = 0;
			Array[i + 1] = 0;
			staff[boss].push_back(i + 1);
		}

		for (int i = 0; i < M; i++) {
			int num, value;
			cin >> num >> value;
			Array[num] += value;
		}

		dfs(1, 0);

		for (int i = 1; i <= N; i++) {
			cout << thank[i] << " ";
		}
	}