[SLOP][KAKAO] 리프 노드 수 최대화
by 
gg582 · 2026-06-05 13:36:03 · 67 views
1. 문제 설명
루트 노드, 리프 노드, 분배 노드로 구성되는 트리가 있습니다. 루트 노드는 자식 노드를 하나만 가지며, 루트 노드가 아닌 노드는 자식 노드를 2개, 3개 또는 0개를 가질 수 있습니다. 자식 노드가 0개인 노드는 리프 노드입니다. 당신은 제한된 조건 하에서 트리를 하나 구성하여 리프 노드를 가능한 한 많이 만들려고 합니다.
트리를 구성하는 규칙은 아래와 같습니다.
루트 노드와 리프 노드를 제외한 나머지 노드를 분배 노드라고 하며, 분배 노드는 자식 노드를 2개 또는 3개를 갖습니다.
분배 노드는 최대
dist_limit개 존재할 수 있습니다.트리에서 같은 깊이에 있는 분배 노드의 자식 노드 수는 모두 같아야 합니다. 노드의 깊이는 루트 노드부터 해당 노드까지의 최단 경로 길이와 같습니다.
모든 리프 노드는 분배도라는 값을 갖습니다. 분배도는 해당 리프 노드의 부모 노드에서 루트 노드까지의 최단 경로 상에 있는 모든 노드의 자식 노드 개수의 곱과 같습니다.
예를 들어, 어떤 리프 노드의 부모층이 위에서부터 순서대로 1개, 3개, 3개로 쪼개졌다면 해당 리프 노드의 분배도는 3 × 3 × 1 = 9가 됩니다.
모든 리프 노드의 분배도는
split_limit보다 작거나 같아야 합니다.
예를 들어 dist_limit가 3이고 split_limit가 6인 경우, 분배 노드의 수를 3개 쓰고 모든 리프 노드의 분배도를 3 × 2 × 1 = 6으로 맞추어 리프 노드의 수를 6개로 만들 수 있습니다. 주어진 조건 하에 리프 노드의 수를 6개보다 많이 만드는 트리 구성은 존재하지 않습니다.
최대 몇 개의 분배 노드를 놓을 수 있는지 나타내는 정수 dist_limit, 분배도의 최댓값을 나타내는 정수 split_limit가 매개변수로 주어집니다. 주어진 조건 하에서 만들 수 있는 트리의 리프 노드 수의 최댓값을 return 하도록 solution 함수를 완성해 주세요.
2. 제한사항
- 0 ≤
dist_limit≤ 10^9 - 1 ≤
split_limit≤ 10^9
3. 테스트 케이스 구성 안내
각 그룹은 하나 이상의 하위 그룹으로 이루어져 있으며, 하위 그룹의 모든 테스트 케이스를 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.
| 그룹 | 총점 | 추가 제한 사항 |
|---|---|---|
| #1 | 30% | dist_limit ≤ 10, split_limit ≤ 50 |
| #2 | 70% | 추가 제한 사항 없음 |
4. 입출력 예
| dist_limit | split_limit | result |
|---|---|---|
| 3 | 6 | 6 |
| 0 | 10 | 1 |
| 3 | 100 | 7 |
| 5 | 16 | 9 |
5. 입출력 예 설명
입출력 예 #1
문제의 예시와 같습니다. 위층에서 2개(또는 3개)로 쪼갠 뒤 다음 층을 구성하여 리프 노드를 최대 6개 만들 수 있습니다.
입출력 예 #2
dist_limit가 0이므로 분배 노드를 놓을 수 없습니다. 루트 노드의 자식 노드 1개가 트리에서 유일한 리프 노드가 되므로 1을 return 해야 합니다.
입출력 예 #3
다른 트리 구성으로도 리프 노드를 7개 만들 수 있지만 7개보다 많은 리프 노드를 만들 수 있는 트리 구성은 존재하지 않습니다. 따라서 7을 return 해야 합니다.
입출력 예 #4
분배 노드는 최대 5개까지 놓을 수 있지만, 4개까지만 놓는 것도 가능합니다. 9개보다 많은 리프 노드를 만들 수 있는 다른 트리 구성은 존재하지 않으므로 9를 return 해야 합니다.
1. 최종 정답 코드
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
int solution(int dist_limit, int split_limit) {
long long answer = 1;
// i: Number of 3-fold layers (0 to 21)
for (int i = 0; i <= 21; i++) {
long long pow3 = 1;
for (int k = 0; k < i; k++) {
if (pow3 > split_limit) break;
pow3 *= 3;
}
if (pow3 > split_limit && i > 0) break;
// j: Number of 2-fold layers (0 to 31)
for (int j = 0; j <= 31; j++) {
long long pow2 = 1;
for (int k = 0; k < j; k++) {
if (pow2 > split_limit) break;
pow2 *= 2;
}
// Total split value (Leaf node multiplier)
long long cur_split;
if (pow3 > 0 && pow2 > 2000000000LL / pow3) cur_split = 2000000000LL;
else cur_split = pow3 * pow2;
if (cur_split > split_limit) break;
// =================================================================
// TYPE 1: 3-fold layers on TOP, 2-fold layers on BOTTOM
// Geometric series sum:
// Full 3-dist = (3^i - 1) / (3 - 1)
// Full 2-dist = 3^i * (2^j - 1) / (2 - 1)
// =================================================================
long long full_3_dist_t1 = (pow3 - 1) / 2;
long long full_2_dist_t1 = pow3 * (pow2 - 1);
long long req_dist_t1 = full_3_dist_t1 + full_2_dist_t1;
if (req_dist_t1 <= dist_limit) {
if (cur_split > answer) answer = cur_split;
} else {
if (j > 0) {
// Capacity limit reached during the 2-fold layers at the bottom
long long prev_pow2 = pow2 / 2;
long long prev_dist = full_3_dist_t1 + pow3 * (prev_pow2 - 1);
if (dist_limit >= prev_dist) {
long long usable = dist_limit - prev_dist;
// Linear growth in 2-fold layer: +1 leaf per 1 node
long long possible_leaves = pow3 * prev_pow2 + usable * 1;
if (possible_leaves > answer) answer = possible_leaves;
}
} else if (i > 0) {
// Capacity limit reached during the 3-fold layers at the top
long long prev_pow3 = pow3 / 3;
long long prev_dist = (prev_pow3 - 1) / 2;
if (dist_limit >= prev_dist) {
long long usable = dist_limit - prev_dist;
// Linear growth in 3-fold layer: +2 leaves per 1 node
long long possible_leaves = prev_pow3 + usable * 2;
if (possible_leaves > answer) answer = possible_leaves;
}
}
}
// =================================================================
// TYPE 2: 2-fold layers on TOP, 3-fold layers on BOTTOM
// Geometric series sum:
// Full 2-dist = (2^j - 1) / (2 - 1)
// Full 3-dist = 2^j * (3^i - 1) / (3 - 1)
// =================================================================
long long full_2_dist_t2 = (pow2 - 1);
long long full_3_dist_t2 = pow2 * (pow3 - 1) / 2;
long long req_dist_t2 = full_2_dist_t2 + full_3_dist_t2;
if (req_dist_t2 <= dist_limit) {
if (cur_split > answer) answer = cur_split;
} else {
if (i > 0) {
// Capacity limit reached during the 3-fold layers at the bottom
long long prev_pow3 = pow3 / 3;
long long prev_dist = full_2_dist_t2 + pow2 * (prev_pow3 - 1) / 2;
if (dist_limit >= prev_dist) {
long long usable = dist_limit - prev_dist;
// Linear growth in 3-fold layer: +2 leaves per 1 node
long long possible_leaves = pow2 * prev_pow3 + usable * 2;
if (possible_leaves > answer) answer = possible_leaves;
}
} else if (j > 0) {
// Capacity limit reached during the 2-fold layers at the top
long long prev_pow2 = pow2 / 2;
long long prev_dist = (prev_pow2 - 1);
if (dist_limit >= prev_dist) {
long long usable = dist_limit - prev_dist;
// Linear growth in 2-fold layer: +1 leaf per 1 node
long long possible_leaves = prev_pow2 + usable * 1;
if (possible_leaves > answer) answer = possible_leaves;
}
}
}
}
}
return (int)answer;
}
2. 고등학교 눈높이 개념 해설
이 문제는 학교 수학 시간에 배우는 "등비수열의 합" 개념이 트리 구조에 어떻게 적용되는지 보여주는 대표적인 예시입니다.
① 왜 순서를 뒤집어서 두 번 풀어야 할까?
"같은 깊이(층)에 있는 노드들은 자식 수가 모두 같아야 한다"라는 규칙이 있습니다. 즉, 어떤 층은 통째로 3분기 층이고, 어떤 층은 통째로 2분기 층이어야 합니다.
우리가 상상할 수 있는 형태는 크게 두 가지입니다.
- TYPE 1: 위쪽 층들은 전부 3개씩 쪼개고, 아래쪽 층들은 전부 2개씩 쪼개는 트리
- TYPE 2: 위쪽 층들은 전부 2개씩 쪼개고, 아래쪽 층들은 전부 3개씩 쪼개는 트리
테스트 1번(dist_limit=3, split_limit=6)이 바로 TYPE 2 구조였습니다. 위층에서 2개로 쪼갠 뒤(2¹), 그 아래층 노드 2개가 각각 3개씩 쪼개지면(3¹) 분배 노드는 딱 3개(1 + 2)만 쓰면서 리프 노드 6개를 완벽하게 만들어 냅니다. 기존 코드처럼 TYPE 1 구조로만 계산하면 층 전체를 꽉 채우지 못해 손해를 보게 됩니다. 따라서 두 가지 트리를 모두 시뮬레이션해야 정답이 나옵니다.
② 등비수열 합 공식으로 분배 노드 개수 구하기
트리에서 층을 거듭하며 늘어나는 노드의 개수는 등비수열을 이룹니다. 첫째항이 a, 공비가 r인 등비수열의 첫째항부터 제 n항까지의 합 공식 S_n을 이용해 트리에 사용된 총 분배 노드 수를 구합니다. (여기서 분배 노드를 배치하는 첫 층의 시작 노드 수는 항상 a = 1입니다.)
- 등비수열의 합 공식: S_n = a(rⁿ - 1) / (r - 1)
- 3분기 영역 분배 노드 수: 공비가 3이므로 다음과 같습니다.
(3ⁱ - 1) / (3 - 1) = (3ⁱ - 1) / 2
- 2분기 영역 분배 노드 수: 공비가 2이므로 다음과 같습니다.
(2ʲ - 1) / (2 - 1) = 2ʲ - 1
위쪽 층을 다 채우고 나면 아래쪽 영역은 이미 위에서 불어난 노드 수만큼 곱해진 상태에서 시작하므로, TYPE 1의 총 분배 노드 수 req_dist는 아래 식과 같이 결합됩니다.
- TYPE 1 총 분배 노드 수: req_dist = (3ⁱ - 1) / 2 + 3ⁱ × (2ʲ - 1)
③ 층 중간에 재료가 뚝 끊겼을 때 (Linear Growth)
재료(dist_limit)가 부족해서 다음 층을 다 채우지 못하는 else문 내부의 상황입니다.
- 2분기 영역에서 멈췄을 때: 기존 리프 노드 1개를 분배 노드로 바꾸면 자식이 2개 생깁니다. 나 자신(-1)이 사라지고 자식(+2)이 생기므로, 전체 리프 노드는 결과적으로 딱 +1개 늘어납니다. 따라서 남은 재료 하나당 리프 노드가 1개씩 늘어나므로
usable * 1을 더합니다. - 3분기 영역에서 멈췄을 때: 기존 리프 노드 1개를 분배 노드로 바꾸면 자식이 3개 생깁니다. 나 자신(-1)이 사라지고 자식(+3)이 생기므로, 전체 리프 노드는 결과적으로 +2개 늘어납니다. 따라서 남은 재료 하나당 리프 노드가 2개씩 늘어나므로
usable * 2를 더합니다.
수학 공식으로 완벽한 형태의 최댓값을 구하고, 공식이 커버하지 못하는 '자라다 만 트리'의 끝부분 조각들은 1차 함수(더하기) 개념으로 정밀하게 채워 넣는 구조입니다.