시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 1490 | 632 | 446 | 44.779% |
육각수는 육각형을 이용해 정의할 수 있다. 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을 만들기 위해 필요한 육각수 개수의 최솟값을 출력한다.
26
6
1+1+6+6+6+6
130
5
1+28+28+28+45
146858
4
1+1+1326+145530
999999
3
6+258840+741153
1000000
2
285390+714610
145530
1
145530은 269번째 육각수이다.