[BOJ] 2218 - 상자안의 구슬

1. 문제 정리

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

링크를 확인해보세요.

www.acmicpc.net

• 크기가 a인 A 큐와, 크기가 b인 B큐가 주어집니다.
• 각 큐는 1 ~ N 정수로 채워져있습니다.
• 각 큐에 대하여 다음 세 가지 작업을 수행할 수 있습니다.
  1. A큐에서 숫자 하나 제거합니다.
  2. B큐에서 숫자 하나 제거합니다.
  3. A와 B큐에서 숫자 각각 하나꺼내서 score[A.pop()][B.pop()] 점수 만큼 총점에 더합니다.
• 둘 다 더 이상 원소가 남아있지 않을 때까지 위 작업을 반복했을 때 얻을 수 있는 최대 총점을 구해야 합니다.
  • 총점을 얻기 위하여 행해진 작업의 순서도 구해야 합니다.

2. 문제 풀이

아이디어

• A와 B큐를 하나로 묶어서 이차원 배열 board[A][B]로 보면 각 작업을 수행했을 때 좌표의 이동은 다음과 같습니다.
  • board[0][0] - 1번 수행 -> board[1][0]
  • board[0][0] - 2번 수행 -> board[0][1]
  • board[0][0] - 3번 수행 -> board[1][1]
• 여기서 알 수 있는 것은 과거의 좌표는 미래에 다시 영향을 주지 않는다는 것입니다.
  • (0, 0) -> (0, 1) … -> (0, 0) 식을 다시 돌아오는 일은 없다는 것입니다.
• 결국 (a, b)의 값을 한 번 만 계산되며 그게 고정됨을 알 수 있습니다.

결론

• 해당 문제는 DP를 만족하므로 DP를 사용하여 해결합니다.
• DP[a][b]: (a, b)에 도착할 때 얻을 수 있는 최대 점수를 의미.
  • 점화식: DP[a][b] = max(DP[a - 1][b], DP[a][b - 1], DP[a - 1][b - 1])
• CMD[a][b]: (a, b)에 도착했을 때 이전 좌표에서 수행한 작업 번호를 의미.
  • CMD[a][b] 다음 규칙에 따라서 결정 됨.
    • DP[a - 1][b] 최대인 경우 : 1
    • DP[a][b - 1] 최대인 경우 : 2
    • DP[a - 1][b - 1] 최대인 경우 : 3

3. 코드

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


class Main {

    void solve() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //== 입력 받기 및 초기화
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        int[][] score = new int[N][];
        for (int i = 0; i < N; i++) {
            score[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();
        }

        int[] queueA = Arrays.stream(br.readLine().split(" "))
                .mapToInt(v -> Integer.parseInt(v) - 1).toArray();
        int[] queueB = Arrays.stream(br.readLine().split(" "))
                .mapToInt(v -> Integer.parseInt(v) - 1).toArray();

        // DP[a][b] : A의 a 번째 index과 B의 b번째 index에 도달 했을 때 얻을 수 있는 최대 점수
        int[][] DP = new int[A + 1][B + 1];

        // 최대 점수를 얻기 위하여 이전 좌표에서 수행한 작업 번호를 의미.
        int[][] CMD = new int[A + 1][B + 1];

        // [a][0]는 1번 [0][b]는 2번을 수행해야 만 도착 가능.
        for (int a = 1; a <= A; a++) {
            CMD[a][0] = 1;
        }
        for (int b = 1; b <= B; b++) {
            CMD[0][b] = 2;
        }

        //== DP 계산하기.
        for (int a = 1; a <= A; a++) {
            for (int b = 1; b <= B; b++) {
                int base = score[queueA[a - 1]][queueB[b - 1]];

                // 1번 작업을 통하여 현재 위치에 도착한 경우.
                if (DP[a][b] <= DP[a - 1][b]) {
                    DP[a][b] = DP[a - 1][b];
                    CMD[a][b] = 1;
                }

                // 2번 작업을 통하여 현재 위치에 도착한 경우.
                if (DP[a][b] <= DP[a][b - 1]) {
                    DP[a][b] = DP[a][b - 1];
                    CMD[a][b] = 2;
                }

                // 3번 작업을 통하여 현재 위치에 도착한 경우.
                if (DP[a][b] <= DP[a - 1][b - 1] + base) {
                    DP[a][b] = DP[a - 1][b - 1] + base;
                    CMD[a][b] = 3;
                }
            }
        }

        System.out.println(DP[A][B]);
        System.out.println(getPath(CMD, A, B));
    }

    String getPath(int[][] CMD, int sizeA, int sizeB) {
        StringBuilder sb = new StringBuilder();

        while (sizeA >= 0 && sizeB >= 0) {
            if (CMD[sizeA][sizeB] == 1) {
                sb.append("1 ");
                sizeA -= 1;
            } else if (CMD[sizeA][sizeB] == 2) {
                sb.append("2 ");
                sizeB -= 1;
            } else if (CMD[sizeA][sizeB] == 3) {
                sb.append("3 ");
                sizeB -= 1;
                sizeA -= 1;
            } else {
                break;
            }
        }
        return sb.reverse().toString().strip();
    }

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