문제 소개
자연수 N(1 ≤ N ≤ 109)이 주어졌을 때, 이 수를 합성수들의 합으로 표현하되 가능한 한 가장 많은 개수의 항으로 분할하는 것이 목표입니다. 답으로 그 최대 개수를 반환하고, 어떤 방법으로도 분할할 수 없다면 -1을 반환해야 합니다.
예를 들어 입력이 16이라면 출력은 4입니다. 16은 4 + 4 + 4 + 4 또는 8 + 8처럼 여러 방식으로 나타낼 수 있지만, 그중 (4 + 4 + 4 + 4)가 가장 많은 항을 사용하는 분할이기 때문입니다.
해결 전략
합성수 중 가장 작은 값은 4이며, 4·6·9 세 가지 수만 조합해도 충분히 큰 모든 수를 표현할 수 있습니다. 따라서 작은 범위는 미리 동적 계획법(DP)으로 계산해 두고, 큰 입력값은 4를 반복적으로 빼는 방식으로 처리합니다. 전체 흐름은 다음과 같습니다.
- 전처리(pre_calc): 크기 16짜리 테이블을 만들고 모든 위치를 -1로 초기화한 뒤, table[0] = 0으로 설정합니다. 기준이 되는 합성수 배열 v = [4, 6, 9]를 준비합니다.
- i를 1부터 15까지 순회하면서 각 합성수 j(4, 6, 9)에 대해 i ≥ j이고 table[i - j]가 도달 가능한 값(-1이 아님)이라면, table[i]를 table[i - j] + 1과 비교해 더 큰 값으로 갱신합니다.
- 질의 처리(max_summ): n이 16보다 작으면 테이블 값을 그대로 반환합니다. 그렇지 않으면 t = (n - 16) ÷ 4의 몫 + 1로 계산하여, 4를 t번 빼고 남은 값(n - 4t)의 테이블 결과에 t를 더해 반환합니다.
- 메인 로직에서는 pre_calc()으로 테이블을 생성한 뒤 max_summ(table, n)을 호출해 결과를 출력합니다.
구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
global max_val
max_val = 16
def pre_calc():
table = [-1 for i in range(max_val)]
table[0] = 0
v = [4, 6, 9]
for i in range(1, max_val, 1):
for k in range(3):
j = v[k]
if (i >= j and table[i - j] != -1):
table[i] = max(table[i], table[i - j] + 1)
return table
def max_summ(table, n):
if (n < max_val):
return table[n]
else:
t = int((n - max_val) / 4)+ 1
return t + table[n - 4 * t]
n = 16
table = pre_calc()
print(max_summ(table, n))
입력
16
출력
4
동작 원리 정리
이 알고리즘이 올바르게 동작하는 이유는 간단합니다. 항의 개수를 최대화하려면 가능한 한 가장 작은 합성수인 4를 최대한 많이 사용해야 하기 때문입니다. 짝수는 전부 4의 합으로, 홀수는 9 하나와 나머지 4들의 합으로 표현할 수 있으므로 12 이상의 모든 수는 반드시 분할이 가능합니다. 반면 1, 2, 3, 5, 7, 11은 합성수의 합으로 나타낼 수 없어 -1이 반환됩니다.
전처리는 테이블 크기 16 × 기준값 3개로 상수 시간에 끝나며, 이후 각 질의 역시 O(1)에 처리됩니다. 덕분에 N이 최대 109까지 커져도 즉각적인 답을 얻을 수 있습니다.