[백준 C++] 1949번 우수마을

1949번: 우수 마을

문제 요약

문제

N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, 각 길은 방향성이 없어서 A번 마을에서 B번 마을로 갈 수 있다면 B번 마을에서 A번 마을로 갈 수 있다. 또, 모든 마을은 연결되어 있다. 두 마을 사이에 직접 잇는 길이 있을 때, 두 마을이 인접해 있다고 한다. 이 나라의 주민들에게 성취감을 높여 주기 위해, 다음 세 가지 조건을 만족하면서 N개의 마을 중 몇 개의 마을을 ‘우수 마을’로 선정하려고 한다.

1. ‘우수 마을’로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.
2. 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 ‘우수 마을’로 선정할 수는 없다. 즉 ‘우수 마을’끼리는 서로 인접해 있을 수 없다.
3. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, ‘우수 마을’로 선정되지 못한 마을은 적어도 하나의 ‘우수 마을’과는 인접해 있어야 한다. 각 마을 주민 수와 마을 사이의 길에 대한 정보가 주어졌을 때, 주어진 조건을 만족하도록 ‘우수 마을’을 선정하는 프로그램을 작성하시오.

사용 알고리즘

다이나믹 프로그래밍, 트리

입출력

• 입력: 첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 이하이다. 셋째 줄부터 N-1개 줄에 걸쳐서 인접한 두 마을의 번호가 빈칸을 사이에 두고 주어진다.
• 출력: 첫째 줄에 ‘우수 마을’의 주민 수의 총 합을 출력한다. ``` 예제1

입력 7 1000 3000 4000 1000 2000 2000 7000 1 2 2 3 4 3 4 5 6 2 6 7 출력 14000

## 풀이
트리에서 dp를 사용하는 문제이다. dp에는 각 노드의 상태를 각각 저장한다. 우수마을은 인접할 수 없으므로 우수마을로 판별한 경우 자식들이 모두 우수마을이 아닐때의 값을 더하고 우수마을이 아닐경우로 판별한 경우 자식들은 그중 더 큰값을 더하면 된다. 조건 3은 모든 마을의 인구가 1 이상이므로 조건1을 만족하기 위해선 자동으로 만족해진다.

## 어려웠던 점


## 배운 점 / 느낀 점


## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<int> people;
vector<vector<int>> graph;
vector<pair<int, int>> dp;

void dfs(int node, int parent){
    dp[node].first = people[node];
    dp[node].second = 0;
    for(int g : graph[node]){
        if(g == parent){
            continue;
        }
        dfs(g, node);
        dp[node].first += dp[g].second;
        dp[node].second += max(dp[g].first, dp[g].second);
    }
}


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

    cin >> n;
    people = vector<int>(n+1);
    dp = vector<pair<int, int>>(n+1);
    graph = vector<vector<int>>(n+1, vector<int>());
    for (int i = 1; i <= n; i++) {
        cin >> people[i];
    }
    for (int i = 0; i < n-1; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    dfs(1, 0);
    cout << max(dp[1].first, dp[1].second);
    return 0;
}