[BOJ/백준] 27212 - 미팅

27212번: 미팅

---

dp[i][j] = dp[i - 1][j - 1] + W[A[i]][B[j]];

dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
dp[i][j] = Math.max(dp[i][j], dp[i][j - 1]);

---

---

• 제목

미팅

---

• 조건

시간 제한 : 1 초

메모리 제한 : 512 MB 

---

• 문제

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

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

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

---

• 입력

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

둘째 줄부터 C+1번째 줄에서, i+1번째 줄에는 W[i][1], W[i][2], ... , W[i][C]의 값이 순서대로 공백을 사이에 두고 주어진다.
 
C+2번째 줄에는 A대학 학생 N명의 성격 정보를 나타내는 N개의 정수가 공백을 사이에 두고 순서대로 주어진다.
 
C+3번째 줄에는 B대학 학생 M명의 성격 정보를 나타내는 M개의 정수가 공백을 사이에 두고 순서대로 주어진다.

---

• 출력

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

---

• 제한

1 ≤ N ≤ 1000 

1 ≤ M ≤ 1000

2 ≤ C ≤ 16
1 ≤ Ai ≤ C (1 ≤ i ≤ N)
1 ≤ Bi ≤ C (1 ≤ i ≤ M)
 
1 ≤ W[i][j] ≤ 1,000,000,000 (1 ≤ i, j ≤ C)
W[i][j] = W[j][i] (1 ≤ i, j ≤ C)

 

---

예제 입력1	예제 출력1
2 3 2 1 10 10 10 1 2 1 2 2	20

---

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        int[] A = new int[N + 1];
        int[] B = new int[M + 1];
        int[][] W = new int[C + 1][C + 1];
        for (int i = 1; i <= C; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= C; j++) {
                W[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= M; i++) {
            B[i] = Integer.parseInt(st.nextToken());
        }

        long[][] dp = new long[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                dp[i][j] = dp[i - 1][j - 1] + W[A[i]][B[j]];

                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
                dp[i][j] = Math.max(dp[i][j], dp[i][j - 1]);
            }
        }
        System.out.println(dp[N][M]);
    }
}