BOJ(백준) 1949 - 우수마을

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

---

자료구조(트리, 트리의 독립집합)

N개의 노드로 구성된 트리가 있으며, 트리에는 가중치가 있다. 트리의 '독립집합'을 구성할 때, 가장 가중치가 큰 독립집합의 원소 가중치의 합을 구하는 프로그램을 작성하시오.

---

시간복잡도 : O(N)

트리 임을 명시해줬고, 문제에서 트리에 대한 개념적 속성까지 다 명시해줬다.

---

점검해볼 사항

- 트리의 독립집합

- 트리와 DP는 다 후위탐색인가?

https://github.com/jongwuner/Algorithm/blob/master/BOJ/1949.cpp

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
int N, a[10005], dp[10005][2];
vector<int> adj[10005];
int getAnswer(int idx, int from, int opt) {
    int &ret = dp[idx][opt];
    if (ret != -1) return ret;
 
    ret = 0;
    if (opt == 0) {
        for (int next : adj[idx]) {
            if (next != from) {
                int notCho = getAnswer(next, idx, 0);
                int cho = getAnswer(next, idx, 1);
                int val = max(notCho, cho);
                ret += val;
            }
        }
    }
    else if (opt == 1) {
        ret += a[idx];
        for (int next : adj[idx]) {
            if (next != from) {
                ret += getAnswer(next, idx, 0);
            }
        }
    }
    return ret;
}
int main() {
    memset(dp, -1, sizeof(dp));
 
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) scanf("%d", &a[i]);
    for (int i = 1, a, b; i <= N - 1; i++) {
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int notChoiced = getAnswer(1, 0, 0);
    int choiced = getAnswer(1, 0, 1);
 
    printf("%d\n", (choiced >= notChoiced) ? choiced : notChoiced);
    return 0;
}