[백준] 2266. 금고 테스트

1. 문제 설명

N층 빌딩이 있다. 이 빌딩의 F층은 금고를 떨어뜨렸을 때에 부서지는 최소 층이다. 다시 말하면, F층을 포함하여 그 위의 층에서 금고를 떨어뜨리면 무조건 부서지며, F층의 아래층에서 금고를 떨어뜨릴 때에는 금고는 절대 부서지지 않는다. N층에서도 부서지지 않을 수도 있으며, 1층에서도 부서질 수도 있다.

새로 개발한 금고의 견고함을 측정해보기 위해서 K개의 금고를 이용하여 이 빌딩의 F층을 구하려고 한다. 이를 위해서 직접 금고를 떨어뜨려 보면서 그 결과를 확인하려 한다. 금고가 부서진 경우에는 그 금고를 다시 사용할 수 없으며, 부서지지 않았다면 다시 사용할 수 있다.

이런 상황에서 K개의 금고를 가지고 F층이 몇 층이던지 간에 F층을 알아낼 수 있는 최소한의 금고 낙하 회수를 E(N, K)라 하자. 예를 들어 K=1이라면 F를 알아내기 전에 금고가 부서지면 안 되기 때문에 1층부터 차례로 올라가면서 금고를 떨어뜨려야 한다. 따라서 E(N, 1)=N이 된다.

두 정수 N, K가 주어졌을 때 E(N, K)를 구하는 프로그램을 작성하시오.

• 입력
  첫째 줄에 두 정수 N(1 ≤ N ≤ 500), K(1 ≤ K ≤ N)가 주어진다.

• 출력
  첫째 줄에 E(N, K)를 출력한다.

2. 문제 접근

금고가 몇 층에서 떨어졌을 때 안 부셔지는지 임계값을 찾는 문제입니다.

저희는 알고리즘을 공부하는 이성을 갖춘 사람이므로 기본 탐색은 이분 탐색이라 가정할 수 있습니다. 그런데 문제는, 금고를 열심히 부셔서 한 개의 금고만 남게 된다면, 안전했던 가장 낮은 층부터 마지막으로 금고를 부순 층까지 밑에서부터 한 층씩 금고를 계속 떨어뜨려야 합니다. 처음부터 금고가 한 개만 있다면 선택지 없이 1층부터 n층까지 전부 다 떨어뜨려봐야 합니다.

DP 배열을 어떻게 정의하냐에 따라서 다양한 방식의 DP 풀이가 가능합니다.

가장 일반적으로 생각할 수 있는 풀이는 배열의 정의를 $r$ = 남은 금고의 수, $k$ = 탐색 높이일 때, $DP[r][k]$ = 탐색이 필요한 횟수로 놓는 겁니다. 임의의 높이에서 떨어뜨리면 깨지느냐 안깨지느냐 두 경우가 있겠죠. 깨진다면 현재 높이보다 낮은 범위를 탐색하고, 깨지지 않는다면 높게 탐색합니다. 이때 초기값으로 $r$ = 1일때 $DP[1][k] = k$로 첫 행을 초기화 해줍니다.

반대로 DP 배열을 $r$ = 남은 금고의 수, $c$ = 남은 이동 횟수로 정의할 수 있습니다. 이때 $DP[r][c]$ = 탐색 가능한 최대 층수가 됩니다.

또한 이번 문제와 같이 다음 행의 값을 도출하는데 필요한 행의 개수가 한 개라면 메모이제이션도 간단해집니다.

GOG Egg-Dropping Problem 구글링을 하다가 찾은 유사한? 문제입니다. 아니 유사한 게 아니고 100프로 똑같은 문제입니다. 원문을 번역하면서 겨란이 금고가 된 게 아닌가 의심이 되는 부분입니다.

3. 문제 풀이

1. r = 남은 금고의 수 , c = 높이

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

public class Main {
	
	static StringTokenizer st;
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	st = new StringTokenizer(br.readLine());
    	int c = Integer.parseInt(st.nextToken());
    	int r = Integer.parseInt(st.nextToken());
    	
    	int[][] dp = new int[r+1][c+1];
    	for (int i = 0; i <= c; i++) dp[1][i] = i;
    	for (int i = 0; i <= r; i++) dp[i][1] = 1;
    	
    	for (int i = 2; i <= r; i++) for (int j = 2; j <= c; j++) dp[i][j] = Integer.MAX_VALUE;
    	
    	for (int i = 2; i <= r; i++) 
    		for (int j = 2; j <= c; j++) 
    			for (int k = 1; k < j; k++) 
    				dp[i][j] = Math.min(dp[i][j], Math.max(dp[i-1][k-1], dp[i][j-k]) + 1);
    	
    	System.out.println(dp[r][c]);
    	
	}
}

2. r = 금고의 수, c = 필요한 탐색 횟수

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	static int minTrials(int n, int k) {
        int dp[][] = new int[k + 1][n + 1];
        int m = 0; 
        while (dp[m][n] < k) {
            m++;
            for (int x = 1; x <= n; x++) 
                dp[m][x] = 1 + dp[m - 1][x - 1] + dp[m - 1][x];
            
        }
        return m;
    }
 
    public static void main(String[] args) throws IOException {	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	int n = Integer.parseInt(st.nextToken());
    	int k = Integer.parseInt(st.nextToken());
    	
        System.out.println(minTrials(k, n));
    }
}

3. 2번 메모이제이션 최적화

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int minTrials(int n, int k) {
        int[] dp = new int[n + 1];
        int m;
        for (m = 0; dp[n] < k; m++) 
            for (int x = n; x > 0; x--) 
                dp[x] += 1 + dp[x - 1];
        
        return m;
    }
 
    public static void main(String[] args) throws IOException {	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	int n = Integer.parseInt(st.nextToken());
    	int k = Integer.parseInt(st.nextToken());
    	
        System.out.println(minTrials(k, n));
    }
}