문제

문제 링크

오늘은 A대학의 학생 $N$명과 B대학의 학생 $M$명이 만나는 날이다. 이들이 만나는 장소에는 크고 길이가 긴 식탁이 하나 있어서, 한쪽에는 A대학 학생이, 다른 한쪽에는 B대학 학생이 앉을 예정이다. A대학 학생은 $1$부터 $N$까지, B대학 학생들은 $1$부터 $M$까지 번호가 붙어 있다. 의자에 앉을 때는 번호가 증가하는 순서대로 앉는다.

모든 일정이 끝나면 학생들은 서로 악수를 한다. 한 사람은 최대 한 사람과 악수를 할 수 있다. 이때, 팔이 교차하면 악수를 할 때 불편하기 때문에, 팔이 교차하지 않게 악수를 해야 한다. 악수를 하지 못하는 사람이 생길 수도 있다. 즉, 총 $K$쌍이 생긴 상황에서, 어떤 $i$, $j$ ($1 \leq i < j \leq K$)에 대해, $i$번째 쌍이 A대학의 $x_i$번째, B대학의 $y_i$번째 학생이 악수를 했고, $j$번째 쌍이 A대학의 $x_j$번째, B대학의 $y_j$번째 학생이 악수를 했고 하면 $x_i < x_j$이면 $y_i < y_j$여야 한다.

학생의 성격을 $1$ 이상, $C$ 이하의 정수로 나타낼 수 있다. 성격이 $a$인 사람과 $b$인 사람이 악수를 할 경우, $W[a][b]$만큼의 만족도를 얻는다고 한다. 모든 학생들의 성격을 알고 있을 때, 가능한 만족도의 합의 최댓값을 구하고 싶다. 이를 구하는 프로그램을 작성하라.

입력

첫째 줄에는 $N$, $M$, $C$가 공백을 사이에 두고 주어진다.

둘째 줄부터 $C+1$번째 줄에서, $i+1$번째 줄에는 $W[i][1], W[i][2], \dots, W[i][C]$의 값이 순서대로 공백을 사이에 두고 주어진다.

$C+2$번째 줄에는 A대학 학생 $N$명의 성격 정보를 나타내는 $N$개의 정수가 공백을 사이에 두고 순서대로 주어진다.

$C+3$번째 줄에는 B대학 학생 $M$명의 성격 정보를 나타내는 $M$개의 정수가 공백을 사이에 두고 순서대로 주어진다.

출력

미팅의 만족도의 합으로 가능한 최댓값을 1개의 줄에 걸쳐서 출력한다.

제한

• $1\leq N \leq 1000$ 
• $1\leq M \leq 1000$ 
• $2\leq C \leq 16$ 
• $1\leq A_i \leq C$ ($1 \leq i \leq N$)
• $1\leq B_i \leq C$ ($1 \leq i \leq M$)
• $1\leq W[i][j] \leq 1000000000$ ($1 \leq i, j \leq C$)
• $W[i][j] = W[j][i]$ ($1 \leq i, j \leq C$)

예제 입력

2 3 2
1 10
10 10
1 2
1 2 2

예제 출력

20

풀이

작년 말 원티드 쇼미더코드 2022 3회차의 마지막 문제이다. 당시에 가능한 만족도의 최대합 이라는 글귀를 보고 dp로 풀이해야함을 짐작했지만, 짐작만 하고 풀지는 못했었다.

우선 A대학의 학생이 B학생들에게 악수를 하는 기준으로 DP를 시작했다. DP를 2차원 배열로 만들어 다음과 같이 생각했다.

$dp[i][j]$ = A대학의 $i$번째 학생이 B대학의 $j$번째 학생과 악수할 때 최대 만족값.

A대학 학생과 B학생이 악수를 하는데 제한사항이 있다. 한 사람은 최대 한 사람과 악수할 수 있는 점과, 서로 팔을 교차를 하면 안된다는것이다. 그러므로 dp의 각 원소별 최대값을 구하려면 다음과 같은 3가지 경우의 수를 고려해야 한다. 3가지 경우의 수 중 가장 큰 값이 $dp[i][j]$의 값이 된다.

1. A학교의 $i$학생이 B학교의 $j$학생과 악수 불가능
   1-1. A학교의 $i-1$학생이 B학교의 $j$학생과 악수했을 때 최대 만족값
   1-2. A학교의 $i$학생이 B학교의 $j-1$학생과 악수했을 때 최대 만족값
2. A학교의 $i$학생이 B학교의 $j$학생과 악수 가능
   2-1. A학교의 $i-1$학생이 B학교의 $j-1$학생과 악수했을 때 최대 만족값 + $i$학생과 $j$ 학생이 악수했을 때 만족값

이를 토대로 점화식을 세운다면 다음과 같은 식이 나온다. (satisfaction은 만족값 테이블이다.)

$dp[i][j]$ = Math.max($dp[i][j-1], dp[i-1][j], dp[i-1][j-1] + satisfaction[i][j]$)

이를 토대로 dp의 마지막 원소 배열의 최대값을 구하면 가능한 만족값의 최대값을 구할 수 있게 된다.

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "../ex.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const [N, M, C] = input.shift().split(" ").map(Number);
const satisfaction = [new Array(C + 1).fill(0)];

for (let i = 0; i < C; i++) {
  const cur = input.shift().split(" ").map(Number);
  satisfaction.push([0, ...cur]);
}

const NArr = [0, ...input.shift().split(" ").map(Number)];
const MArr = [0, ...input.shift().split(" ").map(Number)];

const dp = new Array(N + 1).fill(0).map((_) => new Array(M + 1).fill(0));

for (let i = 1; i <= N; i++) {
  for (let j = 1; j <= M; j++) {
    dp[i][j] = Math.max(
      dp[i][j - 1],
      dp[i - 1][j],
      dp[i - 1][j - 1] + satisfaction[NArr[i]][MArr[j]]
    );
  }
}

console.log(Math.max(...dp[dp.length - 1]));