[C++] 27212: 미팅

Baekjoon Online Judge - 27212번: 미팅

문제가 복붙이 안 된당...
c++

풀이

짱 어려운 DP 문제..

먼저 input을 모두 받아준다!
satisfaction[i][j]에는 성격이 i, j인 사람이 만났을 때의 만족도 값이 들어있다.
student_a[ ], student_b[ ]에는 각각 a대학과 b대학의 index번째 학생들의 성격 값이 들어있다.

우리는 만족도의 합이 최대가 되는 값을 구할 것이다! 2차원 DP 배열을 이용하면 된다.

DP[i][j]에 들어있는 값은, a대학 1 ~ i번째 학생들과 b대학 1 ~ j번째 학생들을 미팅시켰을 때의 만족도의 최대값이다.

예시로, A대학 학생 5명, B대학 학생 4명이 미팅을 한다고 가정하자.
아래 그림처럼 A대학의 1번과 B대학의 4번이 악수를 했을 때 만족도가 압도적으로 크다면, 그 합이 최대값일 것이다. 이 경우에는 두 사람만이 악수를 할 수 있다.

혹은 아래 그림처럼 여러 사람이 악수를 했을 때의 만족도의 합이 가장 클 수도 있다.

그래서 (A대학 학생, B대학 학생)의 모든 경우의 수(n * m)를 돌면서, 합의 최대값을 DP배열에 저장할 것이다. DP[i][j]에 들어있는 값은 앞에도 말했듯이 "a대학 1 ~ i번째 학생들과 b대학 1 ~ j번째 학생들을 미팅시켰을 때의 만족도의 최대값"이다.

(x, y)가 악수할 경우를 생각해 보자.
x, y가 악수를 하였을 때(x와 y보다 번호가 높은 학생들은 아직 고려하지 않는다), 최대값이 될 수 있는 값들은 다음과 같다.

1. (x - 1, y)까지의 최대값
2. (x, y - 1)까지의 최대값
3. (x - 1, y - 1)까지의 최대값 + x와 y가 악수했을 때의 만족도

예시를 들면, (x, y)가 각각 3, 4라고 할 때

1번은 초록색 선,
2번은 파란색 선,
3번은 빨간색 선 + 주황색 선을 말한다. 각 선은 해당 악수까지의 최댓값이다.
세 경우는 겹칠 수 없기 때문에, 세 값 중 최댓값이 (3, 4)가 악수하였을 때 최대값이 된다.

따라서

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + 만족도[student_a[i]][student_b[j]])

이다.

모든 경우를 돌고 나면, dp[n][m]에는 n명과 m명이 악수하였을 때의 만족도 합의 최대가 들어있을 것이다. 출력하면 끝!

※주의) 만족도 값의 제한이 1,000,000,000이기 때문에, dp배열에서 합을 구할 때 int범위를 넘어갈 수 있다. long long을 사용해주었다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

void input_data(void);
void find_max(void);

int n, m, c;
int student_a[1001], student_b[1001];
int satisfaction[17][17];
long long dp[1001][1001];

int main(void)
{
	input_data();
	find_max();

	return (0);
}

void input_data(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int i, j;

	cin >> n >> m >> c;
	
	i = 0;
	while (++i <= c)
	{
		j = 0;
		while (++j <= c)
			cin >> satisfaction[i][j];
	}

	i = 0;
	while (++i <= n)
		cin >> student_a[i];
	
	i = 0;
	while (++i <= m)
		cin >> student_b[i];

	return ;
}

void find_max(void)
{
	int i, j;
	
	i = 0;
	while (++i <= n)
	{
		j = 0;
		while (++j <= m)
		{
			long long now_value = satisfaction[student_a[i]][student_b[j]] + dp[i - 1][j - 1];
			dp[i][j] = max({dp[i - 1][j], dp[i][j - 1], now_value});
		}
	}

	cout << dp[n][m] << '\n';

	return ;
}

성공 !