[C++]백준14267번 회사문화 1

문제는 다음과 같다.

오늘은 백준14267번 회사문화 1 문제를 풀어보도록 하자. 처음에 문제이해를 못했다. 그 후 문제이해를 하고도 쌩dfs를 돌려 TLE를 받았다. 어찌보면 당연한 수순이였다. 데이터 값이 10만개니까.. 사원 수 n이 주어져있고 -1 1 2 3 4가 들어왔을 때의 예제밖에 없어서 직속후배는 한 명인줄 알았다.

따라서 상사의 번호를 저장하는 배열 person을 만들어주고 칭찬의 정도를 저장하는 배열 compliment를 만들어주었다. 그 후 for문을 돌리는데 칭찬의 정도를 누적합하면서 계산해주었다.

예시를 보자. 만일 -1 1 1 3 4 4가 들어왔고 3 4, 4 4, 5 5 라는 칭찬이 들어왔다고 하자.

그럼 person배열에는 0 -1 1 1 3 4 4가 저장되어 있고, compliment에는 0 0 0 4 4 5 0이 저장되어 있을 것이다. for문을 1~n까지 돌리는데 person[1] = -1이므로 0을 출력한다.

그 후 person[2] = 1이므로 compliment[2] += compliment[1]을 해주고 compliment[2]를 출력해준다. 이런 식으로 상사의 칭찬을 누적합하면서 상사의 누적칭찬에 본인의 칭찬 값을 더한 것을 갱신하고 출력만 해주면 된다.

                                     [코드]
#include <iostream>
using namespace std;

int person[100001];
int compliment[100001];
int n, m, num, y, x;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		cin >> num;
		if (i == 1) {
			person[1] = -1;
			continue;
		}
		person[i] = num;
	}
	for (int i = 1; i <= m; i++) {
		cin >> y >> x;
		compliment[y] += x;
	}
	for (int i = 1; i <= n; i++) {
		if (i == 1) {
			cout << 0 << ' ';
			continue;
		}
		compliment[i] += compliment[person[i]];
		cout << compliment[i] << ' ';
	}
}