[BOJ 1229] 육각수
View as PDF
Submit solution
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text
Points:
3
Time limit:
2.0s
Memory limit:
128M
Problem types
Allowed languages
육각수는 육각형을 이용해 정의할 수 있다. hn은 한 변에 점 1, 2, ..., n개가 있는 육각형을 점 하나만 겹치게 그렸을 때 존재하는 서로 다른 점의 개수이다.</p>
그림 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
26예제 출력 1
6예제 입력 2
130예제 출력 2
5예제 입력 3
146858예제 출력 3
4예제 입력 4
999999예제 출력 4
3예제 입력 5
1000000예제 출력 5
2예제 입력 6
145530예제 출력 6
1
Comments