문제 요약
루트 노드, 분배 노드, 리프 노드로 이루어진 트리를 구성해야 한다.
루트 노드는 자식 노드를 정확히 1개 가진다.
루트가 아닌 노드는 다음 중 하나다.
- 자식 노드가 0개인 리프 노드
- 자식 노드가 2개인 분배 노드
- 자식 노드가 3개인 분배 노드
분배 노드는 최대 dist_limit개까지 사용할 수 있다.
또한 같은 깊이에 있는 분배 노드들은 모두 같은 개수의 자식 노드를 가져야 한다.
즉, 어떤 깊이에서는 분배 노드들이 모두 2개씩 자식을 가지거나, 모두 3개씩 자식을 가져야 한다.
각 리프 노드는 분배도를 가진다.
분배도는 루트부터 해당 리프의 부모까지 경로에 있는 노드들의 자식 수를 모두 곱한 값이다.
모든 리프 노드의 분배도는 split_limit 이하여야 한다.
목표는 만들 수 있는 리프 노드 수의 최댓값을 구하는 것이다.
핵심 아이디어
깊이별 분배 노드의 자식 수는 2 또는 3이다.
따라서 어떤 깊이까지 완전히 펼쳤을 때 리프 수는 다음 형태가 된다.
2^a × 3^b여기서 a는 2분기 레벨의 개수, b는 3분기 레벨의 개수다.
분배도 역시 경로의 자식 수 곱이므로, 완전히 펼친 리프들의 분배도도 다음과 같다.
2^a × 3^b따라서 split_limit 이하인 2^a × 3^b 값들을 후보로 볼 수 있다.
완전히 펼친 상태
어떤 값 p = 2^a × 3^b까지 완전히 펼쳤다고 하자.
이때 리프 노드 수는 p개다.
이 상태에서 필요한 분배 노드 수를 최소화하려면 2분기 레벨을 먼저 배치하고, 그 다음 3분기 레벨을 배치하는 것이 좋다.
이유는 앞쪽 레벨의 분기 수가 작을수록 다음 레벨에 생기는 노드 수가 적어지기 때문이다.
예를 들어 같은 곱 6을 만드는 방법은 두 가지다.
2 -> 3
3 -> 22 -> 3 순서로 만들면 다음과 같다.
분배 노드 수 = 1 + 2 = 33 -> 2 순서로 만들면 다음과 같다.
분배 노드 수 = 1 + 3 = 4같은 리프 수를 만들 때는 2 -> 3 순서가 더 적은 분배 노드를 사용한다.
완전히 펼치는 데 필요한 분배 노드 수
먼저 2분기 레벨을 a개 펼친다.
필요한 분배 노드 수는 다음과 같다.
1 + 2 + 4 + ... + 2^(a-1)
= 2^a - 1그 후 각 2^a개의 노드 아래에 3분기 레벨을 b개 펼친다.
3분기 레벨에 필요한 분배 노드 수는 다음과 같다.
2^a × (1 + 3 + 3^2 + ... + 3^(b-1))등비수열 합을 사용하면 다음과 같다.
2^a × (3^b - 1) / 2따라서 전체 분배 노드 수는 다음과 같다.
(2^a - 1) + 2^a × (3^b - 1) / 2남은 분배 노드로 한 층 더 일부 확장하기
어떤 곱 p = 2^a × 3^b까지 완전히 펼쳤다고 하자.
현재 리프는 p개다.
분배 노드 예산이 남아 있다면, 다음 깊이에서 일부 리프를 분배 노드로 바꿀 수 있다.
다음 깊이를 2분기로 확장할 수 있으려면 다음 조건이 필요하다.
p × 2 <= split_limit리프 하나를 2분기 분배 노드로 바꾸면 리프 수는 1개 증가한다.
리프 1개 제거 + 자식 2개 생성 = 리프 수 +1다음 깊이를 3분기로 확장할 수 있으려면 다음 조건이 필요하다.
p × 3 <= split_limit리프 하나를 3분기 분배 노드로 바꾸면 리프 수는 2개 증가한다.
리프 1개 제거 + 자식 3개 생성 = 리프 수 +2따라서 완전히 펼친 상태에서 남은 분배 노드 수만큼 다음 층을 일부 확장해볼 수 있다.
전체 풀이 과정
split_limit이하의 2의 거듭제곱들을 만든다.split_limit이하의 3의 거듭제곱들을 만든다.- 모든
2^a × 3^b조합을 확인한다. - 해당 곱까지 완전히 펼치는 데 필요한 분배 노드 수를 계산한다.
- 분배 노드 수가
dist_limit이하라면 리프 수 후보를 갱신한다. - 남은 분배 노드가 있다면 다음 층을 2분기 또는 3분기로 일부 확장해본다.
- 가능한 리프 수의 최댓값을 반환한다.
전체 코드
def solution(dist_limit, split_limit):
powers2 = []
value = 1
while value <= split_limit:
powers2.append(value)
value *= 2
powers3 = []
value = 1
while value <= split_limit:
powers3.append(value)
value *= 3
answer = 1
for pow2 in powers2:
for pow3 in powers3:
product = pow2 * pow3
if product > split_limit:
break
full_nodes = (pow2 - 1) + pow2 * (pow3 - 1) // 2
if full_nodes > dist_limit:
continue
answer = max(answer, product)
remain = dist_limit - full_nodes
if remain == 0:
continue
if product * 2 <= split_limit:
expanded = min(product, remain)
answer = max(answer, product + expanded)
if product * 3 <= split_limit:
expanded = min(product, remain)
answer = max(answer, product + 2 * expanded)
return answer코드 설명
2의 거듭제곱 만들기
powers2 = []
value = 1
while value <= split_limit:
powers2.append(value)
value *= 22^a 값들을 미리 만든다.
split_limit보다 큰 값은 사용할 수 없으므로 그 전까지만 저장한다.
3의 거듭제곱 만들기
powers3 = []
value = 1
while value <= split_limit:
powers3.append(value)
value *= 33^b 값들도 같은 방식으로 만든다.
완전히 펼친 곱 확인
product = pow2 * pow3이 값은 완전히 펼친 상태의 리프 수이자 리프의 분배도다.
split_limit을 넘으면 사용할 수 없다.
if product > split_limit:
break필요한 분배 노드 수 계산
full_nodes = (pow2 - 1) + pow2 * (pow3 - 1) // 2이는 2분기 레벨을 먼저 모두 펼치고, 그 아래에 3분기 레벨을 모두 펼칠 때 필요한 최소 분배 노드 수다.
다음 층 일부 확장
분배 노드가 남아 있다면 다음 층을 일부만 확장할 수 있다.
remain = dist_limit - full_nodes2분기 확장이 가능하면 리프 하나당 리프 수가 1개 늘어난다.
if product * 2 <= split_limit:
expanded = min(product, remain)
answer = max(answer, product + expanded)3분기 확장이 가능하면 리프 하나당 리프 수가 2개 늘어난다.
if product * 3 <= split_limit:
expanded = min(product, remain)
answer = max(answer, product + 2 * expanded)확장할 수 있는 리프는 현재 product개뿐이고, 사용할 수 있는 분배 노드는 remain개뿐이다.
따라서 실제 확장 개수는 다음과 같다.
expanded = min(product, remain)시간 복잡도
split_limit <= 10^9이다.
2의 거듭제곱 개수는 최대 약 30개다.
2^30 > 10^93의 거듭제곱 개수는 최대 약 20개다.
3^20 > 10^9따라서 확인하는 조합 수는 매우 작다.
O(log split_limit × log split_limit)사실상 상수 시간에 가깝다.
공간 복잡도
2의 거듭제곱과 3의 거듭제곱 목록만 저장한다.
O(log split_limit)정리
이 문제의 핵심은 리프의 분배도가 경로의 자식 수 곱이라는 점이다.
자식 수는 2 또는 3만 가능하므로, 완전히 펼친 리프 수와 분배도는 항상 다음 형태가 된다.
2^a × 3^b같은 곱을 만들 때는 2분기 레벨을 먼저 배치하는 것이 분배 노드 수를 최소화한다.
따라서 가능한 2^a × 3^b 값을 모두 확인하고, 남은 분배 노드로 다음 층을 일부 확장하는 경우까지 고려하면 된다.
