문제 푼 날짜 : 2021-10-03

문제

문제 링크 : https://www.acmicpc.net/problem/1949

접근 및 풀이

Tree에서 DP를 이용하여 푸는 문제였다.
이 문제(풀이)와 아주 유사한 문제였다.

이 문제에서는 dp 배열을 아래와 같이 정의하였다.

dp[a][0] = c : a 노드를 정점으로 하면서 a가 우수 마을이 아닐 때, 우수 마을의 주민수의 최댓값.
dp[a][1] = c : a 노드를 정점으로 하면서 a가 우수 마을일 때, 우수 마을의 주민수의 최댓값.

이를 이용해서 dfs로 탐색해주면서 아래의 조건을 유의하면서 각 노드의 상태를 업데이트 해준다.

1. 해당 마을이 우수 마을일 경우, 다음 마을은 반드시 우수 마을이면 안된다.
2. 해당 마을이 우수 마을이 아닐 경우, 다음 마을은 우수 마을이어도 되고 아니어도 된다.
   (이 경우엔 다음 마을이 우수 마을인 경우와 아닌 경우 둘 중에 최댓값을 업데이트해준다.)

코드

// 백준 1949번 : 우수 마을
#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> v[10001];
int resident[10001];
int dp[10001][2];
bool visited[10001];

void dfs(int node) {
    visited[node] = true;
    dp[node][0] = 0; // 해당 노드가 우수 마을이 아닐 경우
    dp[node][1] = resident[node]; // 해당 노드가 우수 마을일 경우

    for (int next : v[node]) {
        if (visited[next]) {
            continue;
        }
        dfs(next);
        dp[node][0] += max(dp[next][0], dp[next][1]);
        dp[node][1] += dp[next][0];
    }
}

int main() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> resident[i];
    }
    for (int i = 0, a, b; i < N - 1; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1);

    cout << max(dp[1][0], dp[1][1]);
    return 0;
}

결과

피드백

유사한 문제를 풀다보면 개념이 어느 정도 잡히면서 재밌다.ㅎㅎ