난이도

Gold 4

문제

육각수는 육각형을 이용해 정의할 수 있다. hn은 한 변에 점 1, 2, …, n개가 있는 육각형을 점 하나만 겹치게 그렸을 때 존재하는 서로 다른 점의 개수이다.

그림 1

그림1은 h1, h2, h3, h4를 의미하며, 처음 육각수 6개는 1, 6, 15, 28, 45, 66이다.

자연수 N이 주어졌을 때, 합이 N이 되는 육각수 개수의 최솟값을 구해보자.

N	최소 개수	합
1	1	1
2	2	1+1
3	3	1+1+1
4	4	1+1+1+1
5	5	1+1+1+1+1
6	1	6
7	2	1+6
8	3	1+1+6
9	4	1+1+1+6
10	5	1+1+1+1+6
11	6	1+1+1+1+1+6
12	2	6+6

1791보다 큰 정수는 항상 육각수 4개의 합으로 만들 수 있다. 또한, 수가 충분히 크다면 항상 육각수 3개의 합으로 만들 수 있다. 또, 최소 개수는 항상 6 이하이고, 이것이 최소인 N은 11과 26밖에 없다. 답이 6인 가장 큰 N은 26, 5인 가장 큰 N은 130, 4인 가장 큰 N은 146858이다.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 N을 만들기 위해 필요한 육각수 개수의 최솟값을 출력한다.

예제 입력

예제 출력

해설

시간초과 날 각오하고 냈는데 맞았다. pypy3의 위력인지.. 여튼 문제 자체를 이해하는 게 가장 어려웠다. 문제의 내용만 이해된다면, 여타 dp문제와 크게 다르지 않다. 육각수는 수학적으로 쉽게 구할 수 있다.

제출 코드

n = int(input())
h = [1]
plus = 5
tmpNum = 1
while(tmpNum < n):
    tmpNum = tmpNum+plus
    plus += 4
    h.append(tmpNum)
#print(h)

#bottom-up 그냥제일 안전함..
d = [0 for i in range(n+1)]
for i in range(1,n+1):
    if(i in h): #육각수 중 하나라면
        d[i] = 1 #한번에 해결 가능
        continue
    j=0
    nom = [] #min을 하기 위한 후보들
    while(i-h[j]>0):
        nom.append(d[i-h[j]]+1)
        j += 1
    d[i] = min(nom)

print(d[n])