[C++] 1949번 우수 마을 - DP, 트리, 트리에서의 DP

1. 문제

• N개의 마을로 이루어진 나라가 있다. 마을에는 1~N까지의 번호가 붙어있다. 이 나라는 트리 구조이며 무방향성이다. N개의 마을 중 몇 개의 마을을 '우수 마을'로 설정하려고 한다.
  1. '우수 마을'로 선정된 마을 주민 수의 총합을 최대로 한다.
  2. '우수 마을'끼리는 서로 인접할 수가 없다.
  3. ;우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과 인접하여야 한다.

<입력>

• - 1 -   \(N(1 \leq N \leq 10,000)\)
• - 2 -   마을 주민 수 \(popu(0 \leq popu \leq 10,000)\)
• - M-1개줄 -   인접한 두 마을의 번호

<출력>

• '우수 마을'의 주민 수 총합

2. 재정의

• 트리에서 최대, 인접 X, 반드시 우수가 아닌 마을은 우수와 인접. 이때 최댓값은?

3. 해결 방법

• dp[no][0] = max(dp[next][1], dp[next][0])
• dp[no][1] = dp[next][1] + popu[no]
• dp[no][0]에서 다음다음 자식 노드가 0이면 no의 다음 자식 노드가 1이 안됨에도 불구하고 max라는 함수에 의해 그리디적인 방법으로 항상 이 경우가 제외되므로 위와 같이 풀 수 있다. (뭔 말인지 모르겠지??ㅋㅋㅋㅋ)

4. 실수한 점, 개선할 점

• 위에 정당성을 증명한다고 꾀나 애먹었다. 애초에 잠도 오는 상황이었으니 뭐.... 실제로 푼 시간을 합치면 한 25분 정도로 아이디어 내고 코딩 시작한 듯.

 

<코드>

#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 10001;

// <문제>
// 마을의 개수 N
int N;
// 마을의 주민 수 popu[]
int popu[MAX_N];

// 트리
vector<int> adj[MAX_N];
// DFS용 방문한 노드 메모 vi
int vi[MAX_N];

// dp
int dp[MAX_N][2];

void input() {
    cin >> N;
    for(int i=1; i<=N; i++)
        cin >> popu[i];
    for(int i=0; i<N-1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

void DFS(int no) {
    vi[no] = 1;
    for(auto next : adj[no]) {
        // 아직 방문하지 못한 곳
        if(!vi[next]) {
            DFS(next);
            // 우수 마을이 아닌 경우
            dp[no][0] += max(dp[next][1], dp[next][0]);
            // 우수 마을인 경우
            dp[no][1] += dp[next][0];
        }
    }
    dp[no][1] += popu[no];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    DFS(1);
    
    cout << max(dp[1][0], dp[1][1]);
    
    return 0;
}

 

<문제 바로가기>

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

1949번: 우수 마을

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.