문제: https://school.programmers.co.kr/learn/courses/30/lessons/468372

리프 노드 수 최대화 풀이 복습

1. 처음 문제를 보고 떠올린 생각

이 문제를 처음 봤을 때는 트리를 직접 만들어가면서 모든 경우를 탐색하면 된다고 생각했었다.

각 노드는 다음 세 가지 상태 중 하나가 될 수 있었다.

자식이 없는 리프 노드
자식이 2개인 분배 노드
자식이 3개인 분배 노드

분배 노드의 개수는 dist_limit을 넘으면 안 되고, 루트에서 리프까지 내려가는 동안 누적되는 분배도는 split_limit을 넘으면 안 된다.

처음에는 현재 깊이에 노드가 여러 개 있다면 그중 몇 개를 분배 노드로 사용할지 모두 선택해야 한다고 생각했었다.

예를 들어 현재 깊이에 노드가 5개 있다면 다음 경우를 모두 확인하는 방식이었다.

1개만 분배하고 4개는 리프로 만든다.
2개를 분배하고 3개는 리프로 만든다.
3개를 분배하고 2개는 리프로 만든다.
4개를 분배하고 1개는 리프로 만든다.
5개를 모두 분배한다.

각 경우마다 다시 2분배와 3분배를 모두 시도하는 DFS를 떠올렸었다.

for (let use = 1; use <= nodes; use++) {
    for (const branch of [2, 3]) {
        // use개의 노드를 branch개씩 분배
    }
}

이 방식은 문제 상황을 그대로 옮긴 완전탐색이었기 때문에 처음 아이디어로는 자연스러웠다.

하지만 깊이마다 분배할 노드 수를 모두 선택하면 경우의 수가 너무 많이 늘어났다.

dist_limit이 작다면 가능하지만, 제한이 커지면 모든 use를 확인하는 방식으로는 통과하기 어렵다고 판단했었다.

2. 처음 DFS 상태를 어떻게 잡았는가

처음에는 DFS의 상태를 다음처럼 생각했었다.

dfs(nodes, used, split, leaf)