금고/문보창 - Revision history

Maintenance script: Table transclusion repair v1

2026-03-27T12:46:20Z

Table transclusion repair v1

← Older revision		Revision as of 12:46, 27 March 2026
Line 4:		Line 4:
	T(n, k) 를 층수 n 과 금고 수 k 일때의 해라 하자. 여기서 n 을 k 개의 금고를 가지고, T(n, k) 횟수 만에 모두 테스트 할 수 있는 건물의 최대높이라 하자.		T(n, k) 를 층수 n 과 금고 수 k 일때의 해라 하자. 여기서 n 을 k 개의 금고를 가지고, T(n, k) 횟수 만에 모두 테스트 할 수 있는 건물의 최대높이라 하자.
	층수가 n 인 건물중 해를 찾는 위치에 첫 금고를 떨어뜨린다고 하자. 그러면 건물은 그 위치 아래와 위로 나뉘어지며, 위쪽은 T(b, k) 가 되고, 아래쪽은 T(a, k-1)이 된다. 여기서 a, b는 첫 금고를 떨어뜨린 위치를 기준으로 나뉘어진 위 아래 건물의 층수다. 여기서 문제의 정의에 따라 우리가 구하고자 하는 해는		층수가 n 인 건물중 해를 찾는 위치에 첫 금고를 떨어뜨린다고 하자. 그러면 건물은 그 위치 아래와 위로 나뉘어지며, 위쪽은 T(b, k) 가 되고, 아래쪽은 T(a, k-1)이 된다. 여기서 a, b는 첫 금고를 떨어뜨린 위치를 기준으로 나뉘어진 위 아래 건물의 층수다. 여기서 문제의 정의에 따라 우리가 구하고자 하는 해는
	~~{{\|~~ max{ T(b, k), T(a, k-1) } + 1 ~~\|}}~~ 이다.		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(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 을 이용하여 값을 구할 수 있다.		T(a+b+1, k) = T(b,k) + 1 = T(a,k-1) + 1
			이다. 여기서 a 와 b 또한 건물의 최대 높이임을 만족해야 한다. 초기값 T(1, k) = 1, T(n, 1) = n 을 이용하여 값을 구할 수 있다.
	== 코드 ==		== 코드 ==
	// Safe		// Safe

Maintenance script: Repair batch-0004 pages from live compare

2026-03-27T00:37:15Z

Repair batch-0004 pages from live compare

← Older revision		Revision as of 00:37, 27 March 2026
Line 14:		Line 14:
	#define MAXN 500		#define MAXN 500

	static int d[MAXN+1][MAXN+1];		static int d[MAXN+1][MAXN+1];
	static int n, k;		static int n, k;

Line 21:		Line 21:
	for (int i = 1; i <= MAXN; i++)		for (int i = 1; i <= MAXN; i++)
	{		{
	d[1][i] = 1;		d[1][i] = 1;
	d[i][1] = i;		d[i][1] = i;
	}		}
	}		}
Line 29:		Line 29:
	{		{
	for (int i = 1; i <= MAXN; i++)		for (int i = 1; i <= MAXN; i++)
	if (value < d[i][k])		if (value < d[i][k])
	return i - 1;		return i - 1;
	return -1;		return -1;
Line 44:		Line 44:
	t = a + b + 1;		t = a + b + 1;
	for (int i = b + 1; i <= __min(t,MAXN); i++)		for (int i = b + 1; i <= __min(t,MAXN); i++)
	d[i][k] = value + 1;		d[i][k] = value + 1;
	value++;		value++;
	}		}
Line 58:		Line 58:
	inline void show()		inline void show()
	{		{
	cout << d[n][k] << endl;		cout << d[n][k] << endl;
	}		}

imported>Unknown at 05:28, 7 February 2021

2021-02-07T05:28:46Z

New page

== 금고 ==
바로 코드 짜면 저번처럼 망해버릴 것만 같아서, 점화식 만들고, 간단히 증명까지 하고 코드를 짰다. 층수 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 을 이용하여 값을 구할 수 있다.
== 코드 ==
// 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;
}
----
[[금고]]