BOJ 1949 : 우수 마을

1949번: 우수 마을 (acmicpc.net)

 

3줄요약

• 트리
• DP

 

문제풀이

 

우리는 문제에서 주어진 3가지 조건들을 만족해나가면서 풀어야 한다.

여기서 우리가 주목해야 할 점은 3번 조건이다. 우리는 약간 생각해보면 3번 조건이 1, 2번 조건에 통합된다는 것을 알 수 있다. 애초에 인접한 마을이 모두 우수 마을이 아니면, 2번 조건이 성립하지 않으므로 그냥 그 마을을 우수 마을로 선정하는 것이 더 이득일 수 있다. 즉, 3번 조건을 만족하지 않는 해가 있다면 그것은 최적의 해가 아니라는 소리다.

이제 진짜 문제풀이로 가보도록 하자.

 

dp[node][a] 를 정의한다. (a = 이 마을을 우수 마을로 설정할 것이면 1, 아니면 0)

 

Top-Down 방식(dfs)로 해결한다:

만약 a가 1이라면, dp[nxt][0] 을 dp[node][a] 에 더한다. (nxt는 다음 노드) 2번 조건이 있기 떄문에 이렇게 한다.

아니라면, max(dp[nxt][0], dp[nxt][1])를 dp[node][a] 에 더한다.

 

코드는 밑에 있다.

 

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> tree[10001];
int vils[10001];
int dp[10001][2];

int dfs(int node, int yes, int old) { // yes = 현재 마을을 우수 마을로 선정했을 경우

    int& cache = dp[node][yes];
    if (cache) return cache;

    for (int i = 0; i < tree[node].size(); i++) {
        int nxt = tree[node][i];
        if (nxt == old) continue;
        if (yes) cache += dfs(nxt, 0, node); // 2번 조건
        else cache += max(dfs(nxt, 0, node), dfs(nxt, 1, node));
        /*
        3번 조건은 신경쓸 필요 없음:
        어짜피 밑에꺼가 이득이면 자동으로 인접하게 되어 있음
        */
    }

    if (yes) cache += vils[node];
    return cache;
}

int main() {

    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> vils[i];
    }

    for (int i = 0; i < N - 1; i++) {
        int from, to; cin >> from >> to;
        tree[from].push_back(to);
        tree[to].push_back(from);
    }

    cout << max(dfs(1, 1, 1), dfs(1, 0, 1)) << endl;
}

 

난이도(개인적): Gold II

난이도(객관적): Gold II