육각수

시간 제한2초메모리 제한128 MB

요약

1부터 1,000,000까지의 N이 주어질 때 육각수(1, 6, 15, 28, ...)들의 합으로 N을 표현하는 데 필요한 최소 개수를 구합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 수학, 정수론, BFS
정답자: 아직 제출이 없습니다

문제

육각수는 육각형 모양으로 점을 배열해 정의한다. $h_n$ 은 한 변에 점이 1개, 2개, ..., $n$ 개인 육각형들을 한 점만 겹치도록 그렸을 때 나타나는 서로 다른 점의 개수이다.

그림은 $h_1$ , $h_2$ , $h_3$ , $h_4$ 를 차례로 나타낸다. 처음 여섯 육각수는 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 이하이며, 최소 개수가 6인 수는 11과 26뿐이다. 답이 6인 가장 큰 수는 26, 답이 5인 가장 큰 수는 130, 답이 4인 가장 큰 수는 146858이다.

입력

첫째 줄에 자연수 $N$ 이 주어진다.

출력

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

제한

$1 \le N \le 1,000,000$

예제6

예제 1
입력
```
26
```
예상 출력
```
6
```
예제 2
입력
```
130
```
예상 출력
```
5
```
예제 3
입력
```
146858
```
예상 출력
```
4
```
예제 4
입력
```
999999
```
예상 출력
```
3
```
예제 5
입력
```
1000000
```
예상 출력
```
2
```
예제 6
입력
```
145530
```
예상 출력
```
1
```