[백준] 1660 캡틴 이다솜 - 동적계획법(Dynamic Programming, DP) + 이분탐색(Binary Search) + 누적합(PrefixSum) JAVA

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

코드설명

동적계획법(Dynamic Programming, DP) + 이분탐색(Binary Search) + 누적합(PrefixSum) 를 활용합니다.

 

이 문제를 보고 동적계획법을 떠올리는 것이 상당히 어려웠습니다.

지금까지 풀어본 문제는 항상 직관적으로 동적계획법이란 것을 알 수 있었는데, 이 문제의 경우 정사면체에서 둘 수 있는 대포알의 개수와 함께 합성되어서 문제가 주어졌기에 떠오리는 것이 어려웠던 것 같습니다. 즉 단순히 대포알 15개가 주어졌다고 그것을 신경쓰는 것이 아닌, 대포알 15개를 어떻게 최소한의 정사면체에 배치할 수 있느냐이기에 그렇습니다

 

문제에서의 함수를 정의해보면,

dfs(n) : n개의 대포알이 주어졌을때 최소한의 개수로 정사면체에 배치하라. 

cache[i] : i개의 대포알이 주어졌을때 최소한의 개수로 정사면체에 배치하라를 Cache합니다.

위와 같이 최적 부분 구조(Optimial Substructure) 형태로 정의합니다.

간단하게 말하면, 결국 완전탐색이고, 그 과정에서 중복연산을 피하라입니다.

 

여기서부턴 처음에 문제를 어떻게 잘못 풀었고, 해결해나가는 생각입니다. (두서없을 수 있음)

처음보고 단순히 누적합과 이분탐색을 활용하면 풀 수 있겠구나라고 생각했습니다.

처음에 잘못 푼 코드에 대해 설명해보겠습니다.

먼저 문제를 보면, 접근방식은 먼저 1 -> 3 -> 6 -> 10 -> 15 형태로 정삼각형들이 한층씩 늘어나는걸 알 수 있었습니다.

이를 보면 한 층씩 늘어난다는 말은 prefixSum[i - 1] + (이번에 늘어날 층의 개수) 임을 알 수 있었습니다.

이를 아래와 같은 코드로 구한뒤,

for(int i=2; ; i++) {
    prefixSum[i] = prefixSum[i-1] + i;
    if(prefixSum[i] >= 300000) {
        hi = i;
        break;
    }
}

문제에서는 최소의 정사면체를 사용하여 구하는 것이므로 누적합으로 각 층마다 정사면체에서 폭탄을 둘 수 있는 위치를 누적합으로 구했습니다.

for(int i=1; i<hi; i++) {
    prefixSum[i] = prefixSum[i-1] + prefixSum[i];
}

그 이후에는 BinarySearch로 마무리지었지요. 이떄 upper-bound로 구현했습니다.

하지만, 예제 5번을 테스트해보니 제가 접근한 방식이 틀렸음을 알았습니다.

input
91

output
answer : 2
wrong : 5

왜 5가 나올까요? 저는 84를 구한뒤 7이 나오는데, 이떄, 84 + 4 + 1 + 1 + 1 로 총 5번의 정사면체가 필요했던 것 입니다.

하지만, 정답에서는 딱 2개의 정사면체를 활용하여 구할 수 있었습니다.

저의 경우 먼저 최대 크기의 정사면체를 구하고서 각각 정사면체에서의 최대 크기를 구함으로써 최대값을 구할 수 있다고 잘못 구한것이지요.

 

해당 오류에 대한 전체 코드입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D;
	static int answer = 0;
	static int[] fibo, prefixSum;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		prefixSum = new int[300000];
		prefixSum[1] = 1;
		int lo = 0;
		int hi = 0;
		for(int i=2; ; i++) {
			prefixSum[i] = prefixSum[i-1] + i;
			if(prefixSum[i] >= 300000) {
				hi = i;
				break;
			}
		}
		
		for(int i=1; i<hi; i++) {
			prefixSum[i] = prefixSum[i-1] + prefixSum[i];
		}
		
		while(N > 0) {
			int temp = binarySearch(lo, hi, N);
//			System.out.println(prefixSum[temp]);
			N -= prefixSum[temp];
			answer += 1;
		}
		System.out.println(answer);
		
	}
	
	static int binarySearch(int lo, int hi, int target) {
		int left = lo - 1;
		int right = hi + 1;
		while(left + 1 < right) {
			int mid = (left + right) / 2;
			if(prefixSum[mid] <= target) {
				left = mid;
			} else if(prefixSum[mid] > target) {
				right = mid;
			}
		}
		return right - 1;
	}
}

 

그러면 어떻게 해야할까요? 

이제 해당 사항을 재귀 + 메모이제이션을 통하여 해결할 수 있습니다.

예로들어, 만약 30이라는 숫자가 주어졌을때, 30개의 대포알을 최소한의 정사면체를 활용하여 만들 수 있는 경우는 정해져있는 것을 알 수 있습니다.

즉, 한번 연산하고서 문제가 분할되어 다시 한번 30 이라는 숫자가 나왔을때 더이상 연산하지 못하도록 하는 것 입니다.

예를들어 90 = 60 + 30 과 90 = 30 + 30 + 30 에서 30의 연산을 중복제거해주는 것이지요.

코드

정답코드입니다. 시간제한에 턱걸이로 맞았습니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D;
	static int answer = 0;
	static int[] fibo, prefixSum;
	static int lo = 0;
	static int hi = 0;
	static int[] cache = new int[300001];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		prefixSum = new int[300000];
		prefixSum[1] = 1;
		Arrays.fill(cache, -1);
		for(int i=2; ; i++) {
			prefixSum[i] = prefixSum[i-1] + i;
			if(prefixSum[i] >= 300000) {
				hi = i;
				break;
			}
		}
		
		for(int i=1; i<hi; i++) {
			prefixSum[i] = prefixSum[i-1] + prefixSum[i];
		}
		System.out.println(dfs(N));
		
	}
	
	static int dfs(int n) {
		if(n == 0) return 0;
		if(cache[n] != -1) return cache[n];
		
		int maxValue = binarySearch(lo, hi, n); //prefixSum의 index를 알 수 있습니다.
		int ret = 300001;
		for(int i=1; i<=maxValue; i++) {
			if(n - prefixSum[i] >= 0) {
				ret = Math.min(ret, dfs(n - prefixSum[i]) + 1);
			}
		}
		
		return cache[n] = ret;
	}
	
	static int binarySearch(int lo, int hi, int target) {
		int left = lo - 1;
		int right = hi + 1;
		while(left + 1 < right) {
			int mid = (left + right) / 2;
			if(prefixSum[mid] <= target) {
				left = mid;
			} else if(prefixSum[mid] > target) {
				right = mid;
			}
		}
		return right - 1;
	}
}