[백준] 1660: 캡틴 이다솜 (DP) - JAVA

https://www.acmicpc.net/problem/1660

 

 

# 문제

캡틴 이다솜은 자신의 해적선에 적을 공격하기 위한 대포알을 많이 보관해 놓는다. 다솜이는 미적감각이 뛰어나기 때문에, 대포알은 반드시 사면체 모양으로 쌓아놓아야 한다고 생각한다. 사면체를 만드는 방법은 길이가 N인 정삼각형 모양을 만든다. 그 위에 길이가 N-1인 정삼각형 모양을 얹고 그위에 계속 해서 얹어서 1크기의 정삼각형 모양을 얹으면 된다.

예를 들어, 사이즈가 3크기의 한 더미 모양은 다음과 같다.

  X

  X
 X X

  X
 X X
X X X

각각의 삼각형은 1, 3, 6, 10 ,..... 와 같이 대포알을 가지고 있다. 따라서 완벽하게 쌓았을 때, 한 사면체에는 1, 4, 10, 20 ,.... 개를 가지고 있을 것이다.

현재 다솜이의 해적선에 대포알이 N개가 있다. 다솜이는 영식이를 시켜서 사면체를 만들게 하고 싶다. 영식이는 물론 하기 싫지만 어쩔수 없이 다솜이가 시키는대로 사면체를 가능한 최소 개수 만큼 만들려고 한다. N개의 대포알로 만들 수 있는 사면체의 최소 개수를 출력하는 프로그램을 작성하시오.

 

# 예제

입력 :  첫째 줄에 입력 N이 들어온다. N은 300,000보다 작거나 같은 자연수이다.

91

 

출력 :  첫째 줄에 영식이가 만들 수 있는 사면체 개수의 최솟값을 출력한다.

2

 

# 필요개념

 

크게 두 부분으로 나누어 문제를 풀었다.

1. 사이즈 당 더미에 필요한 대포알 개수 (1, 4, 10, 20 ..) -> dp[]

2. 대포알 개수당 (N) 만들 수 있는 최소한의 더미 개수 -> cnt[]

 

1번에 대한 점화식을 구하는 건 어렵지 않았다.

dp[idx] = dp[idx - 1] + (dp[idx - 1] - dp[idx - 2]) + idx;

 

개인적으로 어려웠던 부분은 2번 부분이었는데, "대포알 개수 당" 을 기준으로 구할 생각을 한참이나 하지 못했다. 어쩌면 애초에 두 부분으로 나눌 생각을 못 한 걸지도 .. ? 

 

만약 대포알이 13개가 있다고 가정한다. 그러면 처음에 나는 dp배열에서 13보다 작은 수 중 최대값인 10을 픽스한 후, 나머지 3을 이용해 더미를 만드는 경우의 수를 다시 구하는 방식으로 했다. 하지만 이렇게 하면 N이 91일 때 오답이 된다. 

 

N = 91이면, dp[7] = 84이므로 고정하고, 나머지인 7을 이용해 탑을 쌓으면 총 dp[7] + dp[2] + dp[1] + dp[1] + dp[1] 로 5가 되지만 사실 정답은 dp[5] + dp[6]이 된다. 무작정 최대를 찾으면 안 된다는 뜻이다. 

 

무작정 최대를 찾지 않고 모든 dp의 값을 이용해 최솟값을 구한다. dp의 인덱스가 가장 작은 경우부터 돌면서 현재 값과 새로운 값 중 최솟값을 넣으면서 문제를 풀었다. 식으로 작성하면 아래와 같다.

cnt[i] = Math.min(cnt[i], cnt[i - dp[j]] + 1);

 

이렇게 쓰면 현재 대포알 개수와 dp의 값이 같은 경우에는 cnt[i]가 1로 들어간다.

 

# Code

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[125];
        dp[0] = 0;
        dp[1] = 1;

        int idx = 1;
        while(dp[idx] <= N) {
            idx++;
            dp[idx] = dp[idx - 1] + (dp[idx - 1] - dp[idx - 2]) + idx;
        }

        int[] cnt = new int[N + 1];
        Arrays.fill(cnt, Integer.MAX_VALUE);
        cnt[0] = 0;
        cnt[1] = 1;
        for (int i = 2 ; i <= N ; i++) {
            for (int j = 1 ; j < idx ; j++) {
                if (dp[j] > i) break;
                cnt[i] = Math.min(cnt[i], cnt[i - dp[j]] + 1);
            }
        }
        System.out.println(cnt[N]);
    }
}

# 결과