[Java] 백준 1229번 : 육각수

 

문제

육각수는 육각형을 이용해 정의할 수 있다. 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번째 육각수이다.

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader bf;
	private static StringTokenizer st;
	
	private static int N;
	private static int dp[];
	
	public static void main(String[] args) throws NumberFormatException, IOException {

		bf=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(bf.readLine());
		dp=new int[N+1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		
		int idx=0;
		int diagram=diagramNum(idx);
		for(int i=1;i<=N;i++) {
			int next=diagramNum(idx+1);	// 다음 크기의 육각수 점 개수
			if(i==next) {	// 현재 값이 다음 육각수의 점 개수와 같으면 1을 저장하고 다음으로 넘어감
				dp[i]=1;
				continue;
			}
			if(i>next) idx++;	// 현재 값이 다음 육각수의 점 개수보다 크면, 해당 육각수부터 처음 육각수까지 탐색하며 구하는 값이 최소인 경우를 찾음
			for(int j=idx;j>=0;j--) {
				diagram=diagramNum(j);
				if(dp[diagram]==Integer.MAX_VALUE) continue;
				dp[i]=Math.min(dp[i-diagram]+dp[diagram], dp[i]);
				
			}
		}
		
		System.out.println(dp[N]);
	}

	public static int diagramNum(int n) {
		if(n<=0) return 0;
		return 2*n*n-n;
	}
}