[쇼미더코드 3회] 백준 27212 - 미팅 (자바 java)

 문제 : boj27212

---

 

필요 알고리즘 개념

• DP (동적 계획법)
  
  • 약간 생각이 필요한 DP 문제였다. 

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  쇼미더코드 3회 당시 1, 2번 15분만에 풀어놓고 이것만 1시간정도 걸렸다. 생긴게 이분 그래프 형태라 그래프쪽으로 자꾸 생각해보다가 오래걸렸다. 확실히 난 DP에 약한 것 같다 ㅠ. DP로 풀면 되겠는데?! 라고 깨닿기까지 너무 오래걸렸다 ㅋㅋ

 

  입력이 아래와 같다고 해보자.

3 4 3
1 2 3
3 2 1
10 5 1
1 2 3
1 2 3 2

 

  이 때 아래처럼 2차원 배열로 한번 생각해보자. 이하 배열을 arr이라 할 때, arr[i][j] == W[A[i]][B[j]] 를 뜻한다. (A[], B[]는 입력으로 주어진 A대학과 B대학 각 N명과 M명의 성격 정보 배열이다.). 이건 결국 행이 A대학 학생, 열이 B대학 학생의 번호를 뜻하고, 해당 두 대학이 만났을 때의 만족도를 뜻한다. 즉 arr[1][3] = 3 이고 A대학 1번 학생과 B대학 3번 학생이 만났을 때 만족도가 3이라는 의미이다.

 

  여기서 '팔이 교차되지 않게 악수'를 하는건 어떤걸 뜻할까? 항상 아래 행은 위의 행에서 고른 것보다 더 높은 열을 골라야 함을 뜻한다. 즉, 아래 처럼 고르는게 불가하다.

 

가능한 경우의 몇 가지 예는 다음과 같다.

 

  즉, 이 문제는 arr[][] 처럼 배열을 정리했을 때, 각 행에서 0개 혹은 1개의 값을 고를 때 각 행마다 이전 행에서 뭔가 골랐다면 그 열보다 더 큰 값의 열을 골라 그 합들의 최대치를 찾는 문제가 된다. (예를들어 위 이미지에서 상단 우측의 경우 A대학 1번 학생은 아무와도 악수를 하지 않았고, A대학 2번 학생은 B대학 2번 학생과 악수했고, A대학 3번 학생은 B대학 4번 학생과 악수했다.)

 

  그럼 이제 arr[][]과 함께 dp[x][y] 를 정의해보자. dp[x][y]는 A대학 x번, B대학 y번 학생까지 생각했을 때 가능한 가장 큰 만족도 값으로 정의한다. 수식으로 나타내면 다음과 같이 나타내볼 수 있다.

dp[x-1][y-1]+arr[x][y]

  이번 A대학 x번, B대학 y번이 악수를 하는 경우이다. 악수를 하므로 현재 값에 해당하는 만족도(arr[x][y])만큼 증가하고, 이 경우 dp[x-1][y-1] 즉 위의 행의 이전 열까지의 만족도에다가 현재 악수를 한 만족도를 더한 것으로 얻을 수 있다. 참고로 코드에서는 'dp[i-1][j-1] + w[arrA[i]][arrB[j]]' 라고 되어있다. 이건 arr[i][j] == W[A[i]][B[i]] 이기 때문이고, 내 경우엔 arr을 생략하고 바로 진행했으므로 코드에 저렇게 넣어져 있다.

 

dp[i-1][j], dp[i][j-1]

  이번에 악수를 하지 않는 경우이다. 이 경우 이번에 아예 악수를 하지 않는 경우(dp[i-1][j])와, 이번에 이미 이전 열의 B대학 학생과 악수를 한 경우(dp[i][j-1] -> 물론 이전 열에서 악수를 하지 않았을 수도 있다. 아무튼 이번에 악수를 안할꺼니 했던 안했던 상관이 없다.)

  

  dp[x][y]는 위에서 설명한 값들 중 최대치를 고르면 된다.

 

  그럼 최종적으로 답은 dp[N][M]이 될 것이다.

 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private long max(long n1, long n2, long n3) {
        return Math.max(n1, Math.max(n2, n3));
    }

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int tmp = Integer.parseInt(st.nextToken());
        int[][] w = new int[tmp+1][tmp+1];
        for (int i = 1; i <= tmp; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= tmp; j++) {
                w[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int[] arrA = new int[r+1];
        int[] arrB = new int[c+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= r; i++) arrA[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= c; i++) arrB[i] = Integer.parseInt(st.nextToken());

        long[][] dp = new long[r+1][c+1];
        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                dp[i][j] = max(dp[i-1][j-1] + w[arrA[i]][arrB[j]], dp[i-1][j], dp[i][j-1]);
            }
        }

        System.out.println(dp[r][c]);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}