[Java] BOJ1660_캡틴 이다솜

www.acmicpc.net/problem/1660

1660번: 캡틴 이다솜

---

dp1에는 층마다의 대포수가 담겨있고 이 dp1을 이용하여 사면체의 대포수를 담은 배열이 dp2이다.

 

이 dp2를 이용해 결과 배열을 만들었다.

 

예를 들어 5개의 대포알을 가지고 있다고 할 때 4개의 대포알로 만들 수 있는 경우의 수에 1개의 대포알로 만들 수 있는 경우 1을 더한 값과, 1개의 대포알로 만들 수 있는 경우의 수에 4개의 대포알로 만들 수 있는 경우 1을 더한 값의 최솟값이 res [5]에 세팅된다.

 

 

import java.io.*;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] dp1 = new int[122];
		int[] dp2 = new int[122];
		dp1[1] = 1;
		dp2[1] = 1;
		for (int i = 2; i < 122; i++) {
			dp1[i] = dp1[i-1] + i;
			dp2[i] = dp1[i] + dp2[i-1];
		}
		int[] res = new int[N+1];
		Arrays.fill(res, Integer.MAX_VALUE);
		res[0] = 0;
		res[1] = 1;
		for (int i = 2; i <= N; i++) {
			
			for (int j = 1; j < 122; j++) {
				if(dp2[j] > i) break;
				res[i] = Math.min(res[i], res[i - dp2[j]]+1);
			}
		}
		System.out.println(res[N]);
	}

}