문제 링크
문제
티어: 골드 2
알고리즘: dp
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)를 출력한다.
풀이
K개의 금고를 가지고 있을 때 F층이 몇 층이던지 간에 F층을 알아낼 수 있는 최소한의 금고 횟수를 구해야 한다. E(N, K)
그래서 만약 N이 4이고, K가 1인 경우
F층이 4층일 때(최악의 경우) 금고를 4번 낙하 시켜야 하기 때문에 E(4, 1)은 4고 일반화하면 E(N, 1)이 N임을 알 수 있다.
K가 2인 경우 직관적으로 봤을 때는 반씩 줄여나가는게 최선의 방법이라고 생각했다. 그러면 최악의 경우가 반씩 줄어들기 때문이다. (예제가 함정이다..)
그런데 이러한 생각은 틀렸다.
예를 들어 N이 10이고 K가 2인 경우를 보자
최대한 반씩 줄이는 방법이라면 5층이나 6층이기 때문에 총 6회임을 알 수 있다.
그런데 4층에서 시작한 경우는 6보다 더 작은 횟수를 가진다.
4층에서 금고를 낙하한다. 그러면 깨진 경우와 깨지지 않은 경우로 나눠진다.
깨지지 않은 경우 1~3층까지 탐색해야 하는데 금고가 하나이기 때문에 횟수는 4가 된다.
깨진 경우는 5~10층까지 탐색해야 하고, 금고가 2개이기 때문에 다시 금고 하나를 이용해서 줄여줄 수 있다.
두 번째 낙하지점을 7층으로 한다면, 다시 깨진 경우와 깨지지 않은 경우로 나눠지고
깨진 경우는 5~6까지 금고 하나로 탐색해야 하기 때문에 총 횟수는 4가 된다.
깨지지 않은 경우는 8~10층이고 금고가 2개이기 때문에 다시 금고 하나를 이용해서 줄여 준다.
결국 최악의 경우에도 총 횟수 4가 되며, 무조건 반으로 줄이는게 정답이 아니라는 걸 알 수 있다. 그래서 최대한 갈라져 나온 여러 경우가 작은 값을 유지하는게 핵심이다. 아무리 특정 경우가 작더라도 최악의 경우의 수가 크면 그 답은 최적이 아니기 때문이다.
그러면 최선의 시작 지점을 어떻게 찾아야 할까? 그냥 전부 해보면 된다. 그런데 최적 해를 찾는 과정에서 반복되는 구조가 있기 때문에 이러한 경우는 메모제이션으로 재사용해야 시간 초과없이 답을 구할 수 있다.
반복되는 구조는 탐색하는 층 수가 같고, 금고의 수가 같은 구조이며, 한 번만 구해놓고 재사용하면 된다.
그래서 dp[A][B]는 A -> 층 수, B -> 남은 금고의 수로 정의할 수 있다.
그리고 모든 층 수에서 낙하해 보며, 깨지는 경우와 깨지지 않는 경우로 나누고, 그 중 큰 값이 최악의 경우이기 때문에 그 값을 현재 dp[A][B] 값과 비교하면 된다. (어떤 층부터 시작하느냐에 따라서 값이 다르기 때문에 이 부분에서는 min값으로 업데이트 해야한다.)
이 풀이의 시간 복잡도는 O(N*K)다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static final int MAX = 1000;
static int N,K;
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());
K = Integer.parseInt(st.nextToken());
int[][] dp = new int[N + 1][K + 1];
init(dp);
System.out.println(answer(N, K, dp));
}
static int answer(int end, int leftSafe, int[][] dp) {
if(end == 0) {
//불가능한 경우
return 0;
}
if(leftSafe == 1) {
//1개 남은 경우는 남은 모든 층을 순회해야됨
return end;
}
if(end == 1) {
//층이 하나 남은 경우 낙회 횟수 1
return 1;
}
if(dp[end][leftSafe] != MAX) {
//초기화 값이 아니라면 이미 방문했음을 의미
return dp[end][leftSafe];
}
for(int i=1; i<=end; i++) {
int case1 = answer(i - 1, leftSafe - 1, dp); //깨진 경우
int case2 = answer(end - i, leftSafe, dp); //깨지지 않은 경우
int v = Math.max(case1, case2);
dp[end][leftSafe] = Math.min(dp[end][leftSafe], v + 1);
}
return dp[end][leftSafe];
}
static void init(int[][] dp) {
for(int i=1; i<dp.length; i++) {
for(int j=0; j<dp[i].length; j++) {
dp[i][j] = MAX;
}
}
}
}