[BOJ] 22253번 - 트리 디자이너 호석

백준 22253번 - 트리 디자이너 호석

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1초	1024MB	241	105	82	41.837%

문제

트리를 너무나 사랑하는 효성이는 트리 분재 전문가이다. 효성이가 기르는 모든 트리는 정점과 간선으로 이루어져 있다. 정점은 $1$번부터 $N$번 정점까지 존재하며, 간선은 서로 다른 두 정점을 연결해준다. 정점의 개수는 간선의 개수보다 정확히 한 개가 많으며, 사이클을 이루지 않는다. 트리의 뿌리는 정점 중 하나로, 모든 정점 중 가장 낮은 높이에 존재한다. 항상 1번 정점이 트리의 뿌리임이 보장되고, 이파리란 연결된 간선이 1개 이하인 정점을 의미한다. 정점이 뿌리에 가까울수록 낮은 높이에 존재하며, 멀수록 높은 높이에 존재한다.

효성이가 기르는 트리는 특별하기 때문에, 각 정점에 $0$ 이상 $9$ 이하의 정수가 적혀 있다. 어느 날 문득 크리스마스 트리를 만들고 싶어진 효성이는 1개 이상의 정점을 골라서 전구를 달고 싶어졌다. 이 때, 정점을 고르는 방법은 뿌리에서 특정 이파리까지 가는 경로 위에서 고르는 것이다. 이 때 고른 전구들이 꼭 연속적으로 존재할 필요는 없다. 전구가 달린 정점들은 불빛이 들어오면서 정점에 적혀 있던 숫자가 밝게 빛나게 된다.

제일 왼쪽 그림이 효성이가 가지고 있는 나무라고 하자. 가운데와 오른쪽 그림은 올바르게 전구를 고른 예시이다. 각 그림에서 밝혀진 전구에 적힌 숫자를 아래부터 순서대로 읽으면 ${0, 0, 8}$ 과${3, 6, 3}$ 이 된다.

만약 고른 전구가 1번, 7번, 10번이라면 왼쪽과 같은데, 이런 경우에는 뿌리부터 특정 이파리까지의 경로 위에서 고른 것이 아니기 때문에 올바르지 못한 방법이다. 같은 이유로 4번, 5번, 8번, 9번 전구들을 골라도 안 된다.

트리 디자이너 호석은 효성이의 요구 사항을 들은 뒤에 한 가지 문제를 생각해냈다. 전구를 달았을 때, 낮은 높이부터 높은 높이까지 순서대로 숫자를 보았을 때, 오름차순을 만족하도록 전구를 다는 경우의 수는 몇 가지인지 궁금해졌다. 오름차순 수열이란 각 수가 이전보다 작아지지 않는 수열을 의미한다. 즉, 이전과 수가 같아도 여전히 오름차순을 만족한다. 예를 들어 ${0, 0, 8}$은 오름차순이지만 ${3, 6, 3}$은 오름차순이 아니다.

효성이의 나무 정보가 주어졌을 때, 호석이가 궁금한 결과를 계산해보자.

입력

첫 번째 줄에는 정점의 개수 $N$이 주어진다.

두 번째 줄에는 1$1$번부터 $N$번 정점에 써 있는 숫자가 공백으로 구분되어 주어진다. 각 숫자는 $0$ 이상 $9$ 이하의 자연수 이다.

세 번째 줄부터 $N-1$개의 줄에 걸쳐서 각 간선이 잇는 두 정점의 번호가 주어진다.

주어지는 나무는 하나의 연결된 그래프임이 보장된다.

출력

전구를 달 수 있는 경우의 수를 10억 7로 나눈 나머지를 출력하라.

제한

• $1 ≤ N ≤ 100,000$ 

예제 입력1

4
1 1 2 2
1 2
3 2
3 4

예제 출력1

15

예제 입력2

10
3 3 2 0 2 9 6 0 8 1
6 1
1 3
3 7
2 7
4 9
4 8
1 8
10 8
8 5

예제 출력2

22

출처

출처

알고리즘 분류

• 다이나믹 프로그래밍
• 그래프 이론
• 그래프 탐색
• 트리
• 깊이 우선 탐색
• 트리에서의 다이나믹 프로그래밍

접근 방법

낮은 높이 부터 높은 높이까지 전구를 오름차순으로 다는 모든 경우의 수를 구하기 위해 아래와 같이 생각할 수 있다.

• 특정 노드를 선택하였을 때의 경우의 수
• 특정 노드를 선택하지않을 때의 경우의 수

특정 노드를 선택한다면, 하위 노드에서 해당 노드의 값(val[] ) 미만의 값을 선택할 수 없다.

해당 사실을 통해 그래프 탐색을 진행할 때, 이전까지 뽑은 값의 최댓값을 유지해야 한다. 해당 값을 $k$로 두자.

노드의 수가 $1 \leq N \leq 100,000$ 인 것을 감안하였을 때, 일반적인 그래프 탐색으로는 문제를 시간 제한 내에 해결할 수 없다는 것을 알 수 있다. 문제의 최적해를 찾기 위해 그래프 탐색을 하면서 중복되는 부분 문제들이 매우 많이 발생한다는 것을 감안하여 해당 문제를 top-down 방식과 dp를 이용하여 해결하는 것이 적절하다.

이 때 하나 이상의 전구를 선택하는 경우는 루트 노드인 $1$번 노드부터 깊이 우선 탐색을 시작할 때, 특정 노드를 선택하느냐(opt = 1 ) 선택하지 않느냐(opt = 0)에 대한 모든 경우의 수를 더한 것이라는 것을 알 수 있다.

해당 노드를 선택할 수 있는 경우는, 이전까지 뽑은 값의 최댓값($k$) 보다 크거나 같은 경우에만 가능하다. 이 경우를 잘 분기해준다면 $[24,27]$ 번 줄과 같이 표현할 수 있다.

해당 노드를 선택할 수 없는 경우는, 이전까지 뽑은 값의 최댓값($k$)을 유지하며 탐색을 동일하게 진행한다.

해당 문제를 메모이제이션을 적절히 활용하여 해결한다면, 각각의 state는 최대 $2 * 100,005 * 15$ 만큼 존재한다는 것을 알 수 있고, 시간 제한 내에 state를 채울 수 있다는 것을 알 수 있다.

소스코드

#define FASTIO cin.tie(0)->sync_with_stdio(false), cout.tie(0)
//////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
long long N, val[100005], dp[2][100005][15];
vector<int> adj[100005], tree[100005];
void makeTree(int prev, int cur){
    for(auto next : adj[cur]){
        if(next != prev){
            tree[cur].push_back(next);
            makeTree(cur, next);
        }
    }
}
int dfs(int opt, int j, int k){
    long long &ret = dp[opt][j][k];
    if(ret != -1)
        return ret;
    ret = 0;
    for(auto child : tree[j]){
        ret += dfs(0, child, k);
        ret %= MOD;
        if(val[child] >= k) {
            ret += dfs(1, child, val[child]);
            ret %= MOD;
        }
    }
    ret += opt;
    ret %= MOD;
    return ret;
}
int main(void){
    FASTIO;
//////////////////////////////////////////////////////////////////
    cin >> N;

    for(int i=1; i<=N; i++)
        cin >> val[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);
    }

    makeTree(0, 1);
    memset(dp, -1, sizeof(dp));
    cout << (dfs(0, 1, 0) + dfs(1, 1, val[1])) % MOD;
    return 0;
}