[백준 1006] 습격자 초라기 - JAVA

문제 : https://www.acmicpc.net/problem/1006

접근 방법

이 문제는 이해하는데는 어렵지 않았지만 문제를 해결하는데에는 많은 어려움이 있었습니다.
가장 먼저 생각했던 것은 원형을 평면으로 표현하고
맨 처음 열과 맨 마지막 열에 대한 엣지 케이스를 처리한다면 쉽게 풀릴 것으로 생각했습니다.

그러나 이 문제는 저처럼 문제를 풀지도 않고
처음부터 최적화를 고민하는 사람에게는 매우 어려운 문제였습니다.

그도 그럴게 제가 풀었던 일반적인 DP 문제들은 대부분 한 번의 순회로 문제를 해결하는 경우가 많았고 이 문제 또한 억지로 한 번의 순회로 문제를 해결하려다가 많은 시간을 빼앗겼습니다..

또한 DP 에서는 당연하게 그림을 그려가며 경우의 수를 점화식을 세우는 것이 기본인데
알고 있으면서도 모니터만 멀뚱멀뚱.. 코드에다가 주석만 조금씩 끄적였으니..
이 문제를 계기로 반성하게 되었습니다 ㅎㅎ..

그래서 뒤늦게 경우의 수를 그림을 그려 확인했습니다.

이 문제는 원형으로 되어 있는 상태를 평면으로 피면서 자른 0번 열과 N-1번 열에 대해 4가지 경우로 나눠 문제를 풀어야 합니다.

• $0$번 열과 $N-1$번 열이 연결되지 않은 경우
• $0$번 열과 $N-1$번 열이 상단만 연결된 경우
• $0$번 열과 $N-1$번 열이 하단만 연결된 경우
• $0$번 열과 $N-1$번 열이 모두 연결된 경우

이 $4$가지 경우를 각각 타입을 나누어 그림으로 보겠습니다.

Type 1) $0$번 열과 $N-1$번 열이 연결되지 않은 경우

$dp$의 인덱스는 가장 위에 있는 전부 개별 그림과 같습니다.

$N-1$과 연결되지 않아 평면과 같이 일반적인 경우입니다.

제약이 없어 모든 경우의 수가 다 가능하고 예외 케이스가 없는 경우입니다.
다만 type1만이
전부 가로 연결과 전부 세로 연결과 좌측 세로 연결이 가능합니다.

전부 가로 연결은 Type1만이 가능하며 예외처리를 해주어야 하는데 다음과 같습니다.

• 0행과 1행 모두 가로로 인접할 수 있는가?
  - if (canCoverRow(0, i-1, i) && canCoverRow(1, i-1, i)) 로 처리
• Type이 1이고 0과 인접해있는가?
  - if (!(i == 1 && type != 1)) 로 처리

Type 2) $0$번 열과 $N-1$번 열이 상단만 연결된 경우

Type 3) $0$번 열과 $N-1$번 열이 하단만 연결된 경우

Type2와 Type3는 동시에 설명하겠습니다.
$N-1$과의 가로 연결이 상단 또는 하단 위치에 따라 그 반대 행으로 연결이 가능합니다.

• $N-1$과 상단에 연결되어 있을 경우 또는 Type1인 경우: $0$과 $1$은 하단에 연결될 수 있습니다.
  • 연결되는 경우 : dp[i][1] = Math.min(dp[i][1], dp[i-1][2] + 1)
  • 연결 안되는 경우: dp[i][1] = dp[i-1][0] + 1;
• $N-1$과 하단에 연결되어 있을 경우 또는 Type1인 경우 : $0$과 $1$은 상단에 연결될 수 있습니다.
  • 연결되는 경우: dp[i][2] = Math.min(dp[i][2], dp[i-1][1] + 1)
  • 연결 안되는 경우: dp[i][2] = dp[i-1][0] + 1;

세로 연결은 간단하게 dp[0][0] + canConvertCol(1) ? 1 : 2 연산으로 구할 수 있습니다.

Type 4) $0$번 열과 $N-1$번 열이 모두 연결된 경우

이 경우는 가장 간단하게 현재 열이 세로로 연결할 수 있는지만 판단하면 됩니다.
세로 연결은 간단하게 dp[0][0] + canConvertCol(1) ? 1 : 2 연산으로 구할 수 있습니다.

이렇게 각각에 대한 케이스들을 정리하고
타입별로 $dp$를 수행한 후
각각의 최솟값을 구한 후
그 중 최솟값이 정답이 됩니다.

코드

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

public class Main {
    static StringTokenizer st;
    static int[][] enemy;
    static int N;
    static int W;
    static final int MAX = 10000 * 2;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());

            enemy = new int[2][N];

            for (int i = 0; i < 2; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    enemy[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            if (N == 1) {
                sb.append(canCoverCol(0) ? 1 : 2).append("\n");
            }
            else {
                sb.append(getAnswer()).append("\n");
            }
        }
        System.out.print(sb);
    }

    private static int getAnswer() {
        int answer = scenario(1);
        if (canCoverRow(0, 0, N-1)) {
            answer = Math.min(answer, scenario(2));
        }
        if (canCoverRow(1, 0, N-1)) {
            answer = Math.min(answer, scenario(3));
        }
        if (canCoverRow(0, 0, N-1) && canCoverRow(1, 0, N-1)) {
            answer = Math.min(answer, scenario(4));
        }
        return answer;
    }


    static boolean canCoverCol(int col) {
        return enemy[0][col] + enemy[1][col] <= W;
    }

    static boolean canCoverRow(int row, int c1, int c2) {
        return enemy[row][c1] + enemy[row][c2] <= W;
    }

    static int scenario (int type) {
        int[][] dp = new int[N][3];
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], MAX);
        }

        dp[0][0] = (type == 1 && canCoverCol(0)) ? 1 : 2;
        dp[0][1] = 1;
        dp[0][2] = 1;

        for (int i = 1; i < N; i++) {
            dp[i][1] = dp[i-1][0] + 1;
            dp[i][2] = dp[i-1][0] + 1;

            if (canCoverRow(0, i-1, i)) {
                if (!(i == 1 && (type == 2 || type == 4))) {
                    dp[i][1] = Math.min(dp[i][1], dp[i-1][2] + 1);
                }
            }

            if (canCoverRow(1, i-1, i)) {
                if (!(i == 1 && (type == 3 || type == 4))) {
                    dp[i][2] = Math.min(dp[i][2], dp[i-1][1] + 1);
                }
            }

            dp[i][0] = Math.min(dp[i][1] + 1, dp[i][2] + 1);
            dp[i][0] = Math.min(dp[i][0], dp[i-1][0] + (canCoverCol(i) ? 1 : 2));

            if (canCoverRow(0, i-1, i) && canCoverRow(1, i-1, i)) {
                if (!(i == 1 && type != 1)) {
                    int prev = i >= 2 ? dp[i-2][0] : 0;
                    dp[i][0] = Math.min(dp[i][0], prev + 2);
                }
            }
        }

        if (type == 1) return dp[N-1][0];
        else if (type == 2) return dp[N-1][2];
        else if (type == 3) return dp[N-1][1];
        else return dp[N-2][0];
    } 
}