백준 27212번: 미팅

문제 설명

• https://www.acmicpc.net/problem/27212
• A대학 학생과 B대학 학생이 만종도 총합이 최대한 크도록 악수를 해야 합니다.
  단, 악수할때 팔이 교차하면 안됩니다.

접근법

• 1727번: 커플 만들기와 비슷한 문제입니다.

• dp[i][j] = a학교의 i번째, b학교의 j번째 학생까지 '고려'했을 때의 최대 만족도로 정의할 수 있습니다. dp[i][j]는 dp[i-1][j], dp[i][j-1], dp[i-1][j-1]에 의해 결정됩니다.

  • dp[i-1][j-1]에서는 무조건 i와 j가 악수를 할 수 있습니다.
  • dp[i-1][j]에서는
    • j가 악수를 하고 있다면 j가 추가되어도 i와 j는 악수를 할 수 없습니다.
    • j가 악수를 하고 있지 않으면 i와 j는 악수를 할 수 있습니다.
      이 경우는 dp[i-1][j-1]과 동일합니다.
  • dp[i][j-1]에서는
    • i가 악수를 하고 있다면 i가 추가되어도 i와 j는 악수를 할 수 없습니다.
      i가 악수를 하고 있지 않으면 i와 j는 악수를 할 수 있습니다.
      이 경우는 dp[i-1][j-1]과 동일합니다.

• 이를 통해 다음과 같은 점화식이 만들어집니다.
  dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + W[i][j])

• 기타

  • 실제로 문제를 풀 때는 좀 더 나이브하게 접근했던거 같습니다. ('i가 악수를 하고 있다/ 하고 있지 않다', '하고 있지 않으면 dp[i-1][j-1]과 같다'와 같은 내용을 구체적으로 다 생각하지는 않았던거 같습니다.)

정답

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		int[][] W = new int[C][C];
		for (int i = 0; i < C; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < C; j++) {
				W[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int[] arrA = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arrA[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] arrB = new int[M];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			arrB[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] = Math.max(Math.max(dp[i-1][j], dp[i][j-1]),dp[i-1][j-1]+W[arrA[i-1]-1][arrB[j-1]-1]);					
			}
		}
		
		System.out.println(dp[N][M]);
	}
}