백준 14267 - 회사 문화 1

문제 설명

영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다.

모든 칭찬에는 칭찬의 정도를 의미하는 수치가 있는데, 이 수치 또한 부하들에게 똑같이 칭찬 받는다.

직속 상사와 직속 부하관계에 대해 주어지고, 칭찬에 대한 정보가 주어질 때, 각자 얼마의 칭찬을 받았는지 출력하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 트리 구조로 이루어진 조직도에서 자신이 받은 칭찬을 모든 자식에게 전파했을 때 최종적으로 모든 사람이 받은 칭찬의 양을 구하는 것이다.

 

처음 문제를 풀 때는 자식을 기록하여 자신이 칭찬을 받으면 모든 자식에게 전파하도록 구현했다.

로직에는 문제가 없지만 N, M이 최대 100,000이기 때문에 시간 초과가 발생한다.

따라서, 다른 구현 방법이 필요했다.

힌트는 문제에 있다.

 

입력에 대한 설명을 자세히 읽어보면 "직속 상사의 번호는 자신의 번호보다 작다"라는 문구가 적혀 있다.

이 문구와 트리의 특징을 이용하면 문제를 쉽게 풀 수 있다.

트리는 무조건 한 명의 부모를 갖는다.

그 부모가 자신보다 번호가 작다는 뜻은 작은 번호부터 처리하면 루트부터 처리하는 것과 동일하다는 뜻이 된다.

즉, 작은 번호부터 자신의 부모의 칭찬을 모두 가져오는 방식과 자신이 받은 칭찬을 모든 자식에게 전달하는 방식은 결과가 같다는 뜻이다.

예를 들어 보자.

5 3
-1 1 2 3 4
2 2
3 4
5 6

위의 그림은 최종 상태를 나타낸다.

자신이 받은 칭찬을 자식에게 전파한다면 2번 노드가 받은 칭찬을 3, 4, 5에게 2씩 전달해야 한다.

하지만, 모든 칭찬을 기록해 놓은 뒤 번호가 작은 노드부터 자신의 부모의 칭찬을 모두 가져온다면 3은 2에서 2만큼 받아오며 자신이 받은 4만큼의 칭찬을 더해 총 6만큼의 칭찬을 받는다.

5의 경우에는 자신의 부모인 4에서 6(2+4)을 가져오고 자신이 받은 6을 더해 총 12만큼의 칭찬을 받게 된다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<int> parent;
vector<int> compliment;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout << fixed;

	cin >> N >> M;
	parent.resize(N + 1, 0);
	compliment.resize(N + 1, 0);

	for (int i = 1; i <= N; i++)
	{
		int p;
		cin >> p;

		if (p == -1) continue;

		parent[i] = p;
	}

	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		compliment[a] += b;
	}

	for (int i = 2; i <= N; i++)
	{
		compliment[i] += compliment[parent[i]];
	}

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

	return 0;
}

---