원티드 쇼미더코드 3회차 - C번 미팅

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

27212번: 미팅

양 대학의 N명과 M명이 일렬로 서서 악수를 하는데, 팔이 교차하지 않게 악수를 할 수 있을 때, 서로 얻을 수 있는 만족도 합의 최댓값을 구하는 문제이다. 

처음에 이분그래프인가? 라고 생각도 해보고, 사람 순서대로 악수를 하기 떄문에 백트래킹을 이용해서 조합으로도 풀어봤다(시간초과)

악수를 할 수도 있고, 안할 수도 있기 때문에 경우의 수가 너무 많아지기 때문에 바로 DP 방식을 고민했다. 
악수를 한 경우와 악수를 하지 않을 경우로 나누어서 메모이제이션을 하는 방식으로 풀었다.
(A,B가 악수를 하고 만족도가 증가 or A 한명이 패스 or B 한명이 패스)
점화식은 d[x][y] = max(d[x - 1][y], d[x][y - 1], d[x - 1][y - 1] + w[a[x]][b[y]])

점화식을 세우고 나니 LCS문제라는 것을 알게 되었다

#include <bits/stdc++.h>
using namespace std;
#define FASTIO cin.tie(nullptr)->sync_with_stdio(false)
typedef long long ll;

int n, m, c, w[17][17], a[1001], b[1001];
ll d[1001][1001];

ll solve(int aIdx, int bIdx) {
    if (aIdx >= n || bIdx >= m) return 0;

    ll &ret = d[aIdx][bIdx];
    if (ret != -1) return ret;

    return ret = max({
               ret,
               solve(aIdx + 1, bIdx),
               solve(aIdx, bIdx + 1),
               solve(aIdx + 1, bIdx + 1) + w[a[aIdx]][b[bIdx]],
           });
}

int main() {
    FASTIO;
    cin >> n >> m >> c;
    for (int i = 1; i <= c; ++i) { // i-j 악수했을 때 만족도
        for (int j = 1; j <= c; ++j) {
            cin >> w[i][j];
        }
    }
    for (int i = 0; i < n; ++i) { // a 학생 성격정보
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i) { // b 학생 성격정보
        cin >> b[i];
    }
    memset(d, -1, sizeof(d));
    cout << solve(0, 0);
    return 0;
}