취미로 코딩하기

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

이번에 볼 문제는 백준 1983번 문제인 숫자 박스이다.
문제는 아래 링크를 확인하자.

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

0을 제외한 주어진 숫자 박스의 위쪽 행의 숫자들을 차례대로 저장한 배열을 A, 아래쪽 행의 숫자들을 차례대로 저장한 배열을 B라 하자(1-based). 그리고 dp[n][a][b]를 A배열의 첫 a개의 수와 B배열의 첫 b개의 수를 길이 n의 숫자박스에 채워넣을 때의 가능한 최댓값으로 정의하자. 이 때, 구하고자 하는 값은 dp[N][cntA][cntB]가 된다. (단, cntA는 A의 길이, cntB는 B의 길이이다.)

dp[n][a][b]가 나타내는 상황에서, 숫자박스의 마지막 칸은 다음과 같은 네 경우 중 한가지 방법으로 구성된다:

(1) 위쪽 행에는 A배열의 a번째 수, 아래쪽 행에는 B배열의 b번째 수가 들어간다.

(2) 위쪽 행에는 A배열의 a번째 수, 아래쪽 행에는 0이 들어간다.

(3) 위쪽 행에는 0, 아래쪽 행에는 B배열의 b번째 수가 들어간다.

(4) 위쪽 행에는 0, 아래쪽 행에도 0이 들어간다.

위와 같이 숫자박스를 구성해나갈 경우, 남은 숫자박스의 길이(n)으로 모든 수를 채워 숫자박스를 구성할 수 있는지의 여부(n보다 a가 더 커지거나 하는 등)와 그 때의 최댓값 등을 다시 dp값을 이용해 나타내면 점화식을 얻을 수 있다. 이 점화식을 잘 구현해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N;
int A[401], B[401];
int cntA, cntB;

int dp[401][401][401];
bool visited[401][401][401];

int func(int n, int a, int b) {
	int& ret = dp[n][a][b];
	if (visited[n][a][b]) return ret;
	visited[n][a][b] = 1;
	ret = -1000000007;

	if (a && b) ret = max(ret, func(n - 1, a - 1, b - 1) + A[a] * B[b]);
	if (a && n > b) ret = max(ret, func(n - 1, a - 1, b));
	if (b && n > a) ret = max(ret, func(n - 1, a, b - 1));
	if (n > a && n > b) ret = max(ret, func(n - 1, a, b));
	return ret;
}

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

	for (int i = 0; i < 401; i++) visited[i][0][0] = 1;

	cin >> N;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		if (x) A[++cntA] = x;
	}
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		if (x) B[++cntB] = x;
	}

	cout << func(N, cntA, cntB);
}