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

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

코드

#include <iostream>
#include <vector>
using namespace std;

#define FASTIO  ios::sync_with_stdio(false);cin.tie(NULL);

int n, m;
vector<vector<int>> v;
vector<int> dp;

void spread(int start, int sum) {
	if (v[start].size() == 0) return;
	else {
		for (int t : v[start]) {
			dp[t] += sum;
			spread(t, dp[t]);
		}
	}
}

int main() {
	FASTIO;
	cin >> n >> m;
	
	v.resize(n + 1);
	dp.resize(n + 1, 0);

	for (int i = 1,  up; i <= n; i++) {
		cin >> up;
		if (up == -1) continue;
		v[up].push_back(i);
	}

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

	spread(1, 0);
	for (int i = 1; i <= n; i++) cout << dp[i] << " ";
	return 0;
}

 

설명

내리 칭찬을 반영해서 직원들이 받은 칭찬량을 구하는 문제이다. 먼저 벡터 v에 직원들의 상사-부하 정보를 저장한다. v[상사 번호].push(부하 직원 번호)로 저장해준다. 이후 칭찬 받은 직원 번호와 칭찬 수치를 입력받고 이를 dp 배열에 저장한다.  dp[직원 번호] += 칭찬 수치로  한 명의 직원이 여러 번 칭찬받는 경우도 고려할 수 있도록 한다. 

 

이후 사장의 위치부터 재귀함수를 호출해서 내리칭찬을 수행한다. start 번호를 가진 직원에게 부하가 없다면 내리칭찬이 다 끝난 것이니 이를 재귀함수의 종료 조건으로 설정한다. 부하가 있다면 모든 부하를 대상으로 다시 재귀함수를 호출해서 내리칭찬을 수행한다. 

 

느낀 점

문제를 보자마자 바로 호름을 잡아서 코드를 작성했다. 코드 자체는 길지 않아서 금방 짰는데, 게시판에서 테스트 케이스를 찾아 넣어보면서 반례나 놓친 정보가 있는지 확인했다. 같은 직원이 여러 번 칭찬받을 수 있는 경우를 생각하지 못한 걸 발견해서 바로 dp[a] = b 부분을 dp[a] += b 로 변경했다. 이후 해당 코드를 제출했고, 한 번에 맞았다!