고 ¶
바로 드 면 럼 망릴 것만 같, 만들고, 단 명까 고 드를 다. n, 고 k 라 때, 복 O(nk). 구 값 다면 메모리 모두 더 것다.
¶
T(n, k) 를 n 과 고 k 때 라 . 기 n k 개 고를 가고, T(n, k) 만 모두 는 물 대높라 .
가 n 물 를 는 고를 떨뜨린다고 . 그러면 물 그 래 로 나뉘며, T(b, k) 가 되고, 래 T(a, k-1) 된다. 기 a, b는 고를 떨뜨린 를 기로 나뉘 래 물 다. 기 문 따라 리가 구고 는 는
{{| max{ T(b, k), T(a, k-1) } + 1 |}} 다.
그런데 기 T(b,k) > T(a, k-1) 나 T(b,k) < T(a,k-1) 이라면 n = a + b + 1 인 건물의 층수가 우리가 처음에 가정한 n이 T(n,k) 횟수만에 테스트 할 수 있는 건물의 최대 높이라는 가정과 모순된다. 따라서 T(b,k) = T(a,k-1) 이다. 따라서
{{| T(a+b+1, k) = T(b,k) + 1 = T(a,k-1) + 1 |}} 다. 기 a b 또 물 대 높 만 다. 기값 T(1, k) = 1, T(n, 1) = n 값 구 다.
가 n 물 를 는 고를 떨뜨린다고 . 그러면 물 그 래 로 나뉘며, T(b, k) 가 되고, 래 T(a, k-1) 된다. 기 a, b는 고를 떨뜨린 를 기로 나뉘 래 물 다. 기 문 따라 리가 구고 는 는
{{| max{ T(b, k), T(a, k-1) } + 1 |}} 다.
그런데 기 T(b,k) > T(a, k-1) 나 T(b,k) < T(a,k-1) 이라면 n = a + b + 1 인 건물의 층수가 우리가 처음에 가정한 n이 T(n,k) 횟수만에 테스트 할 수 있는 건물의 최대 높이라는 가정과 모순된다. 따라서 T(b,k) = T(a,k-1) 이다. 따라서
{{| T(a+b+1, k) = T(b,k) + 1 = T(a,k-1) + 1 |}} 다. 기 a b 또 물 대 높 만 다. 기값 T(1, k) = 1, T(n, 1) = n 값 구 다.
드 ¶
~cpp
// Safe
#include <iostream>
using namespace std;
#define MAXN 500
static int d[MAXN+1][MAXN+1];
static int n, k;
void init_table()
{
for (int i = 1; i <= MAXN; i++)
{
d[1][i] = 1;
d[i][1] = i;
}
}
int find_max_n(int k, int value)
{
for (int i = 1; i <= MAXN; i++)
if (value < d[i][k])
return i - 1;
return -1;
}
void fill_cell(int k)
{
int a, b, t, value;
t = value = 1;
while (t < MAXN)
{
b = t;
a = find_max_n(k - 1, value);
t = a + b + 1;
for (int i = b + 1; i <= __min(t,MAXN); i++)
d[i][k] = value + 1;
value++;
}
}
void set_dynamic_table()
{
init_table();
for (int k = 2; k <= MAXN; k++)
fill_cell(k);
}
inline void show()
{
cout << d[n][k] << endl;
}
int main()
{
int nCase;
cin >> nCase;
set_dynamic_table();
for (int i = 0; i < nCase; i++)
{
cin >> n >> k;
show();
}
return 0;
}
