Chopsticks/문보창 - Revision history

Maintenance script: Table transclusion repair v1

2026-03-27T12:46:16Z

Table transclusion repair v1

← Older revision		Revision as of 12:46, 27 March 2026
Line 5:		Line 5:
	\|}		\|}
	가장 큰 젓가락 세트부터 선택한다고 보았을 때, 총 K + 8 번의 선택이 존재하고, 다음 점화식이 나올 수 있다.		가장 큰 젓가락 세트부터 선택한다고 보았을 때, 총 K + 8 번의 선택이 존재하고, 다음 점화식이 나올 수 있다.
	~~{{\|~~ D[a]n-3a+2 ~ (k+9-a)*2 = (L(i) - L(i-1))^2 + min<sub>i+2<=k</sub>{ D[a-1][k] ~~} \|}~~}		D[a]n-3a+2 ~ (k+9-a)*2 = (L(i) - L(i-1))^2 + min<sub>i+2<=k</sub>{ D[a-1][k] }
	각 선택마다 선택할 수 있는 젓가락의 범위를 지정하는 것을 통해, 3개의 젓가락중 가장 큰 젓가락은 신경쓰지 않아도 된다.		각 선택마다 선택할 수 있는 젓가락의 범위를 지정하는 것을 통해, 3개의 젓가락중 가장 큰 젓가락은 신경쓰지 않아도 된다.
	위에서 a 는 각 선택, n 은 젓가락 수, k 는 사람 수. 여기서		위에서 a 는 각 선택, n 은 젓가락 수, k 는 사람 수. 여기서
	~~{{\|~~ min<sub>i+2<=k</sub>{ D[a-1][k] } ~~\|}}~~은 앞의 계산 결과를 이용하여 O(1) 시간만에 계산 할 수 있고, a 는 K + 8 번 있으므로 O(kn) 복잡도가 걸린다.		min<sub>i+2<=k</sub>{ D[a-1][k] }
			은 앞의 계산 결과를 이용하여 O(1) 시간만에 계산 할 수 있고, a 는 K + 8 번 있으므로 O(kn) 복잡도가 걸린다.

	== 코드 ==		== 코드 ==

Maintenance script: Repair batch-0001 pages from live compare

2026-03-26T23:56:04Z

Repair batch-0001 pages from live compare

← Older revision		Revision as of 23:56, 26 March 2026
Line 5:		Line 5:
	\|}		\|}
	가장 큰 젓가락 세트부터 선택한다고 보았을 때, 총 K + 8 번의 선택이 존재하고, 다음 점화식이 나올 수 있다.		가장 큰 젓가락 세트부터 선택한다고 보았을 때, 총 K + 8 번의 선택이 존재하고, 다음 점화식이 나올 수 있다.
	{{\| D[a][[n-3a+2 ~ (k+9-a)*2]] = (L(i) - L(i-1))^2 + min~~<~~sub~~>~~i+2<=k~~<~~/sub~~>~~{ D[a-1][k] } \|}}		{{\| D[a]n-3a+2 ~ (k+9-a)*2 = (L(i) - L(i-1))^2 + min<sub>i+2<=k</sub>{ D[a-1][k] } \|}}
	각 선택마다 선택할 수 있는 젓가락의 범위를 지정하는 것을 통해, 3개의 젓가락중 가장 큰 젓가락은 신경쓰지 않아도 된다.		각 선택마다 선택할 수 있는 젓가락의 범위를 지정하는 것을 통해, 3개의 젓가락중 가장 큰 젓가락은 신경쓰지 않아도 된다.
	위에서 a 는 각 선택, n 은 젓가락 수, k 는 사람 수. 여기서		위에서 a 는 각 선택, n 은 젓가락 수, k 는 사람 수. 여기서
	{{\| min~~<~~sub~~>~~i+2<=k~~<~~/sub~~>~~{ D[a-1][k] } \|}}은 앞의 계산 결과를 이용하여 O(1) 시간만에 계산 할 수 있고, a 는 K + 8 번 있으므로 O(kn) 복잡도가 걸린다.		{{\| min<sub>i+2<=k</sub>{ D[a-1][k] } \|}}은 앞의 계산 결과를 이용하여 O(1) 시간만에 계산 할 수 있고, a 는 K + 8 번 있으므로 O(kn) 복잡도가 걸린다.

	== 코드 ==		== 코드 ==
Line 19:		Line 19:

	static int nPerson, nStick; // 손님수, 젓가락 수		static int nPerson, nStick; // 손님수, 젓가락 수
	static int stick[MAX_STICK+1]; // 젓가락		static int stick[MAX_STICK+1]; // 젓가락
	static int d[2][MAX_STICK+1]; // 다이나믹 테이블		static int d[2][MAX_STICK+1]; // 다이나믹 테이블

	inline int calcDegree(int i)		inline int calcDegree(int i)
	{		{
	int x = stick[i] - stick[i-1];		int x = stick[i] - stick[i-1];
	return x * x;		return x * x;
	}		}
Line 30:		Line 30:
	inline int findMin(int k, int x, int n)		inline int findMin(int k, int x, int n)
	{		{
	int min = d[k][x];		int min = d[k][x];
	for (int i = x + 1; i <= n; i++)		for (int i = x + 1; i <= n; i++)
	if (min > d[k][i])		if (min > d[k][i])
	min = d[k][i];		min = d[k][i];
	return min;		return min;
	}		}
Line 41:		Line 41:
	cin >> nPerson >> nStick;		cin >> nPerson >> nStick;
	for (int i = 1; i <= nStick; i++)		for (int i = 1; i <= nStick; i++)
	cin >> stick[i];		cin >> stick[i];
	}		}

Line 47:		Line 47:
	{		{
	for (int i = nStick - 1; i >= (nPerson + 8) * 2; i--)		for (int i = nStick - 1; i >= (nPerson + 8) * 2; i--)
	d[1][i] = calcDegree(i);		d[1][i] = calcDegree(i);
	d[1][nStick] = MAX_NUM;		d[1][nStick] = MAX_NUM;
	}		}

Line 59:		Line 59:
	i = nStick - 3 * seti + 2;		i = nStick - 3 * seti + 2;
	min = findMin(!(seti&0x1), i+2, nStick - 3 * seti + 5);		min = findMin(!(seti&0x1), i+2, nStick - 3 * seti + 5);
	d[seti&0x1][i] = calcDegree(i) + min;		d[seti&0x1][i] = calcDegree(i) + min;
	for (i = i-1; i >= (nPerson + 9 - seti) * 2; i--)		for (i = i-1; i >= (nPerson + 9 - seti) * 2; i--)
	{		{
	if (min > d[!(seti&0x1)][i+2])		if (min > d[!(seti&0x1)][i+2])
	min = d[!(seti&0x1)][i+2];		min = d[!(seti&0x1)][i+2];
	d[seti&0x1][i] = calcDegree(i) + min;		d[seti&0x1][i] = calcDegree(i) + min;
	}		}
	}		}

imported>Unknown at 05:22, 7 February 2021

2021-02-07T05:22:52Z

New page

== 소감 ==
{| class="wikitable"
|-
| 2006-01-04 Accepted 1.123 500
|}
가장 큰 젓가락 세트부터 선택한다고 보았을 때, 총 K + 8 번의 선택이 존재하고, 다음 점화식이 나올 수 있다.
{{| D[a][[n-3a+2 ~ (k+9-a)*2]] = (L(i) - L(i-1))^2 + min<sub>i+2<=k</sub>{ D[a-1][k] } |}}
각 선택마다 선택할 수 있는 젓가락의 범위를 지정하는 것을 통해, 3개의 젓가락중 가장 큰 젓가락은 신경쓰지 않아도 된다.
위에서 a 는 각 선택, n 은 젓가락 수, k 는 사람 수. 여기서
{{| min<sub>i+2<=k</sub>{ D[a-1][k] } |}}은 앞의 계산 결과를 이용하여 O(1) 시간만에 계산 할 수 있고, a 는 K + 8 번 있으므로 O(kn) 복잡도가 걸린다.

== 코드 ==
// 10271 - Chopsticks
#include <iostream>
using namespace std;

#define MAX_NUM 1000000000
#define MAX_STICK 5003

static int nPerson, nStick; // 손님수, 젓가락 수
static int stick[MAX_STICK+1]; // 젓가락
static int d[2][MAX_STICK+1]; // 다이나믹 테이블

inline int calcDegree(int i)
{
int x = stick[i] - stick[i-1];
return x * x;
}

inline int findMin(int k, int x, int n)
{
int min = d[k][x];
for (int i = x + 1; i <= n; i++)
if (min > d[k][i])
min = d[k][i];
return min;
}

void input()
{
cin >> nPerson >> nStick;
for (int i = 1; i <= nStick; i++)
cin >> stick[i];
}

void initTable()
{
for (int i = nStick - 1; i >= (nPerson + 8) * 2; i--)
d[1][i] = calcDegree(i);
d[1][nStick] = MAX_NUM;
}

void process()
{
int i, min;
initTable();
for (int seti = 2; seti <= nPerson + 8; seti++)
{
i = nStick - 3 * seti + 2;
min = findMin(!(seti&0x1), i+2, nStick - 3 * seti + 5);
d[seti&0x1][i] = calcDegree(i) + min;
for (i = i-1; i >= (nPerson + 9 - seti) * 2; i--)
{
if (min > d[!(seti&0x1)][i+2])
min = d[!(seti&0x1)][i+2];
d[seti&0x1][i] = calcDegree(i) + min;
}
}
cout << findMin((nPerson + 8)&0x1, 2, nStick - 3 * nPerson - 22) << endl;
}

int main()
{
int nCase;
cin >> nCase;
for (int i = 0; i < nCase; i++)
{
input();
process();
}
return 0;
}
----
[[Chopsticks]]