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

본문 링크

#include <iostream>
#include <vector>

using namespace std;

long long dp[100001]={0};

void DFS(int node , vector<vector<int>> &graph , vector<bool> &visit)
{
    visit[node]=true;

    for (auto next_node : graph[node])
    {
        if (!visit[next_node])
        {
            dp[next_node]+=dp[node];
            DFS(next_node , graph , visit);

        }
    }
}

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

    int N,M;
    cin >> N >> M;
    
    vector<vector<int>> graph(N+1);
    vector<bool> visit(N+1);

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

        if (K!=-1)
        {
            graph[K].push_back(i);
        }
    }



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

    DFS(1 , graph ,visit);

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

/*

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

0 246 492 615 615 246
*/

📌 어떻게 접근할 것인가?

재귀를 통해 풀었습니다.

원래 아래에서 위로 올라가면서 가장 위에 도달했을때 함수 뒤에 dp 값을 갱신해줄려 했는데
그냥 위에서 아래로 내려가는동안 dp 값을 매번 갱신해주었습니다.

처음 dp 값을 설정해줄때 칭찬을 같은 사람이 할 수 있으므로

dp[a]=b; // X

dp[a]+=b; // O

위와 같이 갱신해주어야 합니다.

이외에는 딱히 특별한 점은 없으며 그냥 DFS 를 돌려주면서 아래로 내려가며 방문체크를 해주고 dp 값을 증가시켜주면됩니다.