시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB42413810642.400%

문제

육각수는 육각형을 이용해 정의할 수 있다. 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을 만들기 위해 필요한 육각수 개수의 최솟값을 출력한다.

제한

  • 1 ≤ N ≤ 1,000,000

예제 입력 1

26

예제 출력 1

6

1+1+1+1+6+15

예제 입력 2

130

예제 출력 2

5

1+28+28+28+45

예제 입력 3

146858

예제 출력 3

4

1+1+1326+145530

예제 입력 4

999999

예제 출력 4

3

6+258840+741153

예제 입력 5

1000000

예제 출력 5

2

285390+714610

예제 입력 6

145530

예제 출력 6

1

145530은 269번째 육각수이다.

출처