[BOJ 27212 // C++] 미팅

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

 

이번에 볼 문제는 백준 27212번 문제인 미팅이다.
문제는 아래 링크를 확인하자.

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

27212번: 미팅

dp[X][Y]를 A대학의 첫 X명의 학생와 B 대학의 첫 Y명의 학생들끼리 악수를 할 때의 만족도의 최댓값이라 하자.

 

이 때, 최댓값을 구성하는 악수 짝은 (1) A대학의 X번째 학생과 B대학의 Y번째 학생이 서로 악수를 하거나 (2) A대학의 X번째 학생과 B대학의 Y보다 작은 순서의 누군가가 서로 악수를 하거나 (3) A대학의 X보다 작은 순서의 누군가와 B대학의 Y가 서로 악수를 하는 셋 중 하나를 만족시켜야 함을 알 수 있다.

 

위의 각 경우를 dp[X][Y]를 이용한 식으로 나타내어 점화관계를 찾아내고 적절한 메모이제이션을 활용해 문제를 해결해주자.

 

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

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

ll N, M, C;
ll W[17][17];

int arrN[1001], arrM[1001];
ll dp[1001][1001];
ll func(int idxN, int idxM) {
	ll& ret = dp[idxN][idxM];
	if (ret) return ret;
	return ret = max(func(idxN - 1, idxM - 1) + W[arrN[idxN]][arrM[idxM]], max(func(idxN - 1, idxM), func(idxN, idxM - 1)));
}

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

	cin >> N >> M >> C;
	for (int r = 1; r <= C; r++) {
		for (int c = 1; c <= C; c++) {
			cin >> W[r][c];
		}
	}

	for (int i = 1; i <= N; i++) cin >> arrN[i];
	for (int i = 1; i <= M; i++) cin >> arrM[i];

	for (int r = 0; r <= N; r++) dp[r][0] = 1;
	for (int c = 0; c <= M; c++) dp[0][c] = 1;

	cout << func(N, M) - 1;
}