문제 이해

트리 하나가 주어질 것이다.
Root 노드부터 Leaf Node에서 Node에 불을 킬 것인데, Node의 값 기준 "오름차순"으로 불이 켜져야 한다.
(같은 숫자도 오름차순으로 생각한다)

조건은 아래와 같다.
1. Root노드 ~ 1개의 Leaf Node까지 경로에 존재하는 Node들의 불만 끄고 킬 수 있다.
2. Node에 쓰여 있는 숫자 기준 오름차순(같은 수 포함)으로 불을 켜야 한다.
3. Node 불을 킬 수도 있고, 끌 수도 있다(연속적으로 켜야하는 것은 아니다)

위 조건에 맞춰 불을 킬 때, 불을 킬 수 있는 경우의 수를 구하는 문제이다.

---

문제 풀이

Tree & Root -> Leaf Node로 간다는 것을 보았을 때 바로 DFS를 생각하였다.

그런데 문제는 해당 Node가 "켜질지 안켜질지 모르다"는 것이다.

즉, 원래라면 DFS를 수행할 때 종료조건이 존재하는데, 이 문제에서는 사실상 종료 조건이라는 것이 Leaf Node에 다다라 더 이상 갈 수가 없을 때 뿐인 것이다.

정말 이 문제를 해결하기 위해 많은 고민을 하였다.

그리고 이 문제는 최종적으로 Tree에 DP를 접목하여 문제를 풀었다.

그렇다면 DP를 어떻게 적용해야할까?
나는 전구(Node)에 적힐 숫자가 0 이상 9 이하라는 말에 집중했다.
DP[i][j]의 크기를 Node 개수 * 10(0~9개수)로 지정하면 어떨까?

그렇다면 DP[i][j]가 무엇을 의미하는지가 중요해질 것이다.
나는 DP[i][j]를 i번째 Node를 Tree의 Root라고 간주하였을 때 i번째 Node 다음에 바로 켜지는 Node의 숫자를 j라고 지정하였다
만약 {0,1,2}로 켜졌을 때 1을 기준으로 보면 DP[1][2] = 1이 될 것이고, 0을 기준으로 보면 DP[0][1] = 1이 되는 것이다.
(dp[0][2] 같은 경우에는 0다음 1이 꺼지고 2가 켜지는 경우가 존재하므로 이 상황에서 1의 값을 가질 것이다)

즉, DP[i][j]에서 j를 "바로 다음에 켜지는 불"의 Node 크기를 지정함으로써 해당 Node 아래에 있는 Node들은 다시 Search하지 않아도 되도록 한 것이다.

DP[i][j] : i번째 Node에 불이 켜졌을 때 다음에 켜진 Node 크기가 j인 경우
파악하기 제일 어려웠고, 이 문제의 핵심 알고리즘이였다.

---

코드

import java.io.*;
import java.util.*;


public class Main {
	static StringBuilder sb = new StringBuilder();
	static FastReader sc = new FastReader();
	
	static int N;
	static int[] value;
	static long[][] dp;
	static final long MOD = 1000000007;
	
	static ArrayList<Integer>[] edges;
	
	static void make_tree() {
    // 각 Node와 연결된 Node들을 ArrayList에 입력
    // Node들에 할당된 점수(숫자) 지정
		edges = new ArrayList[N+1];
		
		for(int i =0;i<N;i++) {
			int tmp = sc.nextInt();
			value[i+1] = tmp;
			edges[i+1] = new ArrayList<>();
			dp[i+1][value[i+1]] = 1;
		}
		
		for(int i =0;i<N-1;i++) {
			int in = sc.nextInt();
			int out = sc.nextInt();
			
			edges[in].add(out);
			edges[out].add(in);
		}
	}
	
	static void dfs(int now, int parent) {
    // now : 현재 Search할 Node
    // parent : now의 부모 Node
		for(int s:edges[now]) {
			if(s==parent) continue;
			
			dfs(s, now);
            // 자식 Node들에 대한 DFS를 먼저 수행
			
			for(int i =0;i<10;i++) {
				dp[now][i] = (dp[now][i] + dp[s][i])%MOD;
			}
            // 현재 Node에 불을 키지 않는 경우
            // 다음 Node는 0 ~ 9까지 어떤 값을 가져도 불을 킬 수 있음
            // 따라서, dp[now][0] ~ dp[now][9]를 모두 계산해야 한다
            // dp[now]는 자식 노드인 dp[s]를 활용하여 구할 수 있다
			
			for(int i = value[now];i<10;i++) {
				dp[now][value[now]] 
                          = (dp[now][value[now]] + dp[s][i])%MOD;
			}
            // 현재 Node에 불을 키는 경우
            // 다음 Node는 now Node의 수치 이상의 값만 불을 킬 수 있다
            // 따라서, dp[s][현재 Node 수치] ~ dp[s][9]만을 활용해야 한다
		}
	}
	
	public static void main(String[] args) {
		
		N = sc.nextInt();
		
		dp = new long[N+1][10];
		value = new int[N+1];
	
		make_tree();
		
		dfs(1, 0);
		
		int ans = 0;
		for(int i =0;i<10;i++) {
			ans+=dp[1][i];
			ans%=MOD;
		}
		System.out.println(ans);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과