C++ 백준 14267 회사 문화1

백준 14267

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

14267번: 회사 문화 1

풀이 전 나의 생각

상사가 직속 부하를 칭찬하며 그 부하가 부하의 직속 부하를 연쇄적으로

칭찬하는 내리 칭찬이 있을 때, 각자 얼마나 칭찬을 받았는지 구해야한다.

 

조건

-  (2 ≤ n, m ≤ 100,000)

- (2 ≤ i ≤ n, 1 ≤ w ≤ 1,000)

- 1번의 경우, 상사가 없으므로 -1이 입력된다.

- 직속 상사의 번호는 자신의 번호보다 작으며, 최종적으로 1번이 사장이다.

 

과정

문제를 보면 직속 상사의 번호가 먼저 주어지게 되는데

이는 번호가 뒤죽박죽 주어지는 것도 아니고, 숫자의 폭이 크게 주어지는 것도 아닌

-1, 1, 2, 3... 순서의 차례로 주어지기 때문에 직원 번호 앞뒤 관계를 트리로 구성해도 되지만

굳이 트리를 사용하지 않아도 된다. 

 

차례대로 주어지는데, 상사의 번호는 자신의 번호보다 무조건 작다면 변수가 없기 때문에 

트리를 이용한 dfs의 전체 탐색은 오히려 낭비가 될 수 있다. 따라서 반복문과 DP를 사용하여

간단하게 풀이가 가능하다.

 

그럼 DP를 구하려면 현재의 DP 값에 이전의 DP값을 넣어줘야 하니 이전의 값을

넣어줄 수 있는 무언가가 필요하다.

 

이 문제는 친절하게도 주어진 직원 번호가 -1부터 시작하여 두 번째부터 직원 번호가 들어가기 때문에

직원 번호의 배열을 이용하여 이전의 DP값 역할을 해줄 수 있다.

 

ex) DP[2] += DP[직원 번호 배열[2]], 직원 번호 배열[2] = 1 

 

이런  식으로 문제를 풀어나가며 칭찬 정도를 구할 수 있다.

 

1. 직원 번호의 정보를 저장한다.

for (int i = 1; i <= n; i++)
	{
		int n_num;
		cin >> n_num;

		p_num[i] = n_num;
	}

 

2. 칭찬의 수치를 DP 배열에 저장해준다.

void solve()
{
	for (int j = 0; j < m; j++)
	{
		int i, w;
		cin >> i >> w;

		dp[i] += w;
	}
...

칭찬은 내리 칭찬의 형태기 때문에 만약 2번 직원이 칭찬을 2, 3, 5를 받았다고 하면

2번 직원 밑까지 2+3+5의 값을 모두 내리 칭찬해야 하기 때문에 미리 DP배열에 칭찬 수치를 미리 넣어준다.

 

3. 직원 번호가 저장되어 있는 배열을 이용하여 DP값을 갱신해 나간다.

cout << dp[1] << " ";

	for (int i = 2; i <= n; i++)
	{
		dp[i] += dp[p_num[i]];
		cout << dp[i] << " ";
	}

이전에 받을 수 있는 칭찬 수치를 현재 탐색하고 있는 DP 배열에 넣어주며 내리 칭찬의 형태로

DP값을 모두 구해준다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

int p_num[100001];
int dp[100001];
int n, m;

void solve()
{
	for (int j = 0; j < m; j++)
	{
		int i, w;
		cin >> i >> w;

		dp[i] += w;
	}

	cout << dp[1] << " ";

	for (int i = 2; i <= n; i++)
	{
		dp[i] += dp[p_num[i]];
		cout << dp[i] << " ";
	}
}

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

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
	{
		int n_num;
		cin >> n_num;

		p_num[i] = n_num;
	}

	solve();
}