Boj 255714) 점프 쇼다운

문제

백준 25714

이 문제는 풀이 방법이 다양하다.

우선 내가 처음 접근한 방법을 소개하고, 다른 사람이 푼 풀이를 보고 내가 다시 푼 방법을 소개한다.

방법 1

설명

순환배열을 4 파트 이상으로 나누지 않으면서 3 파트만 남도록 제거하는 방법을 구해야한다.

우선 임의의 판을 하나 제거하면 선형배열이 되어 계산하기가 편해진다. n-1 길이의 선형배열에서의 경우의 수에서 n 을 곱하면 답이 된다.

선형배열에서는 경우의 수를 나눈다. Div3(l) 은 길이가 l 인 선형배열을 3 파트로 나누는 경우의 수이다.

• 먼저 제거하는 판이 맨앞 또는 뒤라면 Div3(l-1) 과 같다.
• 그렇지 않다면 판을 a 와 l-a-1 로 쪼개게 된다. 그러면 Div2(a) * Div1(a) 와 Div1(a) * Div2(a) 의 경우로 나눌 수 있다. 이는 한쪽 판을 먼저 처리하고 다른 쪽 판을 계산하는 경우의 수이다. 양쪽을 번갈아가면서 처리하는 경우를 계산하기 위해선 \(\binom{a-1}{l-4}\) 를 결과에 곱해주어야한다.

Div2(l) 과 Div1(l) 역시 비슷하게 계산하면 된다.

시간 복잡도

O(\(\mathrm{N}^2\))

코드

using ll = long long;
const ll MOD = 1e9 + 7;

int64_t ModInv(ll t)
{
	int idx = MOD - 2; int64_t base = t, res = 1;
	while (idx)
	{
		if (idx & 1)  res = (res * base) % MOD;
		base = (base * base) % MOD;
		idx >>= 1;
	}
	return res;
}

ll facts[301], facts_inv[301];
ll dp1[301], dp2[301], dp3[301];

inline ll Div1(int l) { return dp1[l]; }

ll Div2(int l)
{
	if (dp2[l]) return dp2[l];
	if (l <= 2) return l == 2;

	ll& res = dp2[l];
	for (int i = 1; i < l-1; i++)
	{
		ll ddd = facts[l-3] * facts_inv[l-3 - (i - 1)] % MOD * facts_inv[i - 1] % MOD;
		res += Div1(i) * Div1(l - i - 1) % MOD * ddd;
		res %= MOD;
	}
	res += Div2(l - 1) * 2; // 양옆에서 줄어들었을 경우

	return res %= MOD;
}

ll Div3(int l)
{
	if (dp3[l]) return dp3[l];
	if (l <= 3) return l == 3;

	ll& res = dp3[l];
	for (int i = 1; i < l-1; i++)
	{
		ll ddd = facts[l-4] * facts_inv[l-4 - (i - 1)] % MOD * facts_inv[i - 1] % MOD;
		res += Div1(i) * Div2(l - i - 1) % MOD * 2 * ddd % MOD;
	}
	res += Div3(l - 1) * 2; // 양옆에서 줄어들었을 경우

	return res %= MOD;
}

int main()
{
	facts[0] = facts[1] = 1; for (int i = 2; i <= 300; i++) facts[i] = facts[i - 1] * i % MOD;
	facts_inv[300] = ModInv(facts[300]);  for (int i = 300; i >= 1; i--) facts_inv[i-1] = facts_inv[i] * i % MOD;
	dp1[0] = 1; dp1[1] = 1; for (int i = 2; i <= 300; i++) dp1[i] = dp1[i - 1] * 2 % MOD;

	int n;  cin >> n;
	cout << n*Div3(n-1)%MOD << endl;
}

방법 2

설명

dp[0][l] 은 길이가 l 인 선형배열을 중간에 4파트 이상으로 만들지 않고 3 파트만 남기는 경우의 수이다. 이는 방법 1에서 설명한 것과 같이 2*dp[0][l-1] 과 나머지로 표현할 수 있다. 나머지는 우선 중간배열을 하나 제거하고 시작하게 되는데 두 경우로 나눌 수 있다.

• 2 조각으로 나뉘는 경우. dp[2][l]
  • ... 1 ...x... 11 ... 모양을 생각하자. x 는 처음 제거한 위치이고 ... 는 임의의 길의의 제거한 배열이다. 어디를 제거하든 제거할 위치는 변함이 없으므로 dp[2][l+1] = 4*dp[2][l] 의 점화식을 얻을 수 있다. 11 이 처음에 올 수도 있으므로 실제 사용할 땐 2를 곱해야한다.
• 처음 2 파트로 만들고 임의의 단계 후에 3 파트로 만드는 경우. dp[1][l]
  • 이는 길이가 l-1, l-2, ... 인 배열에서 2조각으로 만든 후 여기서 뭉쳐져 있는걸 다시 2조각으로 나누면 된다. 남은 판은 ... 1 ...x... 1 ...x... 1 ... 모양에서 제거하는 것이므로 dp[1][l-1]*6 이 된다. 합치면 dp[1][l+1] = dp[1][l]*6 + 2*dp[2][l] 이 된다.

시간 복잡도

O(\(\mathrm{N}\))

코드

using ll = long long;
const ll MOD = 1e9 + 7;

ll dp[3][350];

int main()
{
	int n; cin >> n;
	dp[0][3] = 1;
	dp[0][4] = 4, dp[1][4] = 2, dp[2][4] = 4;
	for (int i = 4; i < n-1; i++)
	{
		dp[0][i+1] = (dp[0][i]*2 + dp[1][i] + 2*dp[2][i]) % MOD;
		dp[1][i+1] = (dp[1][i]*6 + 2*dp[2][i]) % MOD;
		dp[2][i+1] = dp[2][i]*4 % MOD;
	}
	cout << n*dp[0][n-1]%MOD << endl;
}