취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15245번 문제인 Boom!이다.
문제는 아래 링크를 확인하자.

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

왼쪽부터 접어 폭발물이 왼쪽으로부터 l번째 칸까지 오게(그리고 l번째 칸을 넘기지는 않게) 접는 경우의 수와 오른쪽부터 접어 폭발물이 오른쪽으로부터 r번째 칸까지 오게(그리고 r번째 칸을 넘기지는 않게) 접는 경우의 수를 각각 구할 수 있다면 가능한 모든 l과 r의 쌍들의 경우를 살펴 문제를 해결할 수 있을 것이다. 이와 같은 경우의 수를 DP를 이용해 구해보자. 아래의 서술은 왼쪽에서부터 접는 경우를 기준으로 살펴본다.

dp[C][L]을 "연속해서 C개의 칸에 폭발물이 붙어있는 것이 보이는, 왼쪽으로부터 L번째 칸까지 폭발물이 붙어있는 경우의 수"라 하자. 이 상태로 접기 이전 상태들을 생각해보면, dp[C][L] = dp[C-L][L] + dp[C-L-1][L-1] + ... + dp[C-L-2][L-1] + ... 과 같은 형태의 점화식을 쉽게 떠올릴 수 있다.

이 점화식을 이용해 각 dp[C][L]의 값을 계산해낼 수 있고, 이를 이용하면 폭발물이 왼쪽으로부터 L번째 칸까지 오게(그리고 L번째 칸을 넘기지는 않게) 접는 경우의 수를 각 C별 값을 합하여 계산해낼 수 있다. 이를 이용해 문제를 해결하자.

아래는 제출한 소스코드이다.

#define MOD 10301
#include <iostream>
using namespace std;
typedef long long ll;

int N, A, B;
ll dp1[1001][1001];
bool visited1[1001][1001];
ll total1[1001];

ll dp2[1001][1001];
bool visited2[1001][1001];
ll total2[1001];

ll func1(int i, int j) {
	ll& ret = dp1[i][j];
	if (visited1[i][j]) return ret;
	visited1[i][j] = 1;

	for (int k = 0; k <= i && i - k > 0 && j - i - k > 0; k++) {
		ret += func1(i - k, j - i -  k);
	}

	ret %= MOD;

	return ret;
}

ll func2(int i, int j) {
	ll& ret = dp2[i][j];
	if (visited2[i][j]) return ret;
	visited2[i][j] = 1;

	if (2 * i > j) return ret;

	for (int k = 0; k <= i && i - k > 0 && j - i - k > 0; k++) {
		ret += func2(i - k, j - i - k);
	}

	return ret %= MOD;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> A >> B;
	dp1[A][A] = dp2[B][B] = 1;
	visited1[A][A] = visited2[B][B] = 1;
	for (int i = 1; i < 1001; i++) {
		for (int j = i; j < 1001; j++) func1(i, j);
	}
	for (int i = 1; i < 1001; i++) {
		for (int j = i; j < 1001; j++) func2(i, j);
	}

	for (int j = 1; j < 1001; j++) {
		for (int i = 1; i <= j; i++) {
			total1[j] += dp1[i][j], total2[j] += dp2[i][j];
		}
		total1[j] %= MOD, total2[j] %= MOD;
	}

	ll ans = 0;
	for (int L = 1; L < N; L++) {
		for (int R = 1; L + R <= N; R++) {
			ans += total1[L] * total2[R];
		}
		ans %= MOD;
	}

	cout << ans;
}