백준[1949] 우수마을

문제 설명

풀이 방법

이 문제는 트리 + dp를 이용하는 문제이다. dp는 dp[현재 노드 번호][현재 노드가 우수인지 아닌지 여부]로 정의한다.

2번 조건에 의해 현재 노드가 우수 마을이면 항상 다음 노드는 우수 마을이 아니고, 우수마을이 아니라면 다음 노드는 우수마을일수도 있고 아닐 수도 있다.

3번 조건은 1번 조건에 의해 자연스럽게 만족된다. 우수x -> 우수x -> 우수x 이런식으로 계속해서 될 수 있다고 착각을 하여 시간을 많이 뺏겼다. 하지만 우수x -> 우수x -> 우수x 이 상황은 항상 올 수 없다. 왜냐하면  우수x -> 우수x -> 우수x 이 상황보다 우수x -> 우수 -> 우수x 이 상황이 항상 더 크기 때문에 최댓값을 유지하기 위해서는 우수x가 계속해서 올 수 없다.

 

코드

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;
vector<vector<int>> v, tree;
int cost[10004], dp[10004][2], visited[10004];

//그래프를 단방향 그래프로 바꿔준다
void dfs(int cur) {
    visited[cur] = true;
    for (auto nxt : v[cur]) {
        if (!visited[nxt]) {
            tree[cur].push_back(nxt);
            dfs(nxt);
        }
    }
}

int dpf(int cur, int great) {
    int &ret = dp[cur][great];
    if (ret != -1) return ret;
    int ans = 0;
    if (great) { 	//현재 노드가 우수 마을인 경우
        for (auto nxt : tree[cur]) {
            ans += dpf(nxt, 0);
        }
        return ret = ans + cost[cur];
    } else {		//현재 노드가 우수마을이 아닌 경우
        for (auto nxt : tree[cur]) {
            ans += max(dpf(nxt, 0), dpf(nxt, 1));
        }
        return ret = ans;
    }
}

int main() {
    int N; scanf("%d", &N);
    v.resize(N + 1); tree.resize(N + 1);
    for (int i = 1; i <= N; i++) {
        scanf("%d", cost + i);
    }
    for (int i = 0; i < N; i++) {
        int a, b; scanf("%d %d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    
//트리는 어느 점이든 루트노드로 만들 수 있기 때문에 편의를 위해 임의로 1번 노드를 루트로 잡고 단방향그래프로 바꿨다.
    dfs(1);
    memset(dp, -1, sizeof(dp));
    printf("%d", max(dpf(1, 0), dpf(1, 1)));
}