2266번: 금고 테스트

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


$O(n^2m)$

(n,k) 에서 i번째 높이에 금고를 떨어뜨렸다고 해보자.
깨졌을 경우 (i-1,k-1)+1
안 깨진 경우 (n-i,k)+1 회일 것이다.
이 중 최악의 경우를 생각해야하므로 i번째 높이에 떨어뜨려 얻을 최소한의 금고 낙하 회수는 max((i-1,k-1),(n-i,k))+1이다.
가능한 i중 최소 낙하 회수를 취하면 되므로
(n,k)=min(i)(max((i-1,k-1),(n-i,k))+1)이다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_N = 500;
int n, m, dp[MAX_N + 1][MAX_N + 1];
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) dp[i][1] = i;
    for (int i = 1; i <= n; i++)
        for (int j = 2; j <= m; j++) {
            dp[i][j] = 1e9;
            for (int k = 1; k <= i; k++)
                dp[i][j] = min(dp[i][j], max(dp[k - 1][j - 1], dp[i - k][j]) + 1);
        }
    printf("%d", dp[n][m]);
    return 0;
}