백준 1006번: 습격자 초라기 (Java)

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

1006번: 습격자 초라기

 

 

 

 

 

 

 

---

 

그 유명한 '습격자 초라기' 문제입니다. DP 문제라는건 예전에 들어서 알았는데도 풀이 접근조차 못하겠더라고요. 그래서 casterian님의 풀이를 봤습니다. 이 분 글 퀄리티가 좋습니다.

 

cf) 안 되는 풀이

처음에 풀이 아이디어를 대충 본 후, '1~N열에서 최솟값, 2~N열 + 1열에서 최솟값을 구하여 두 값의 최솟값이 정답이 되지 않나?' 라고 생각했는데 이 아이디어는 틀렸습니다.

반례)

1

3 8

3 10 5

3 5 10

정답: 4

 

풀이

편의상 1행, 1열부터 시작하여 총 2개의 행, N개의 열이 있다고 합시다.

 

2차원 선형 배열에서의 최솟값

일단은 원형으로 연결되어있는 것을 고려하지 않고, 최소 특수 소대의 수를 구해보도록 합니다.

e를 각 위치별 적의 위치를 저장하는 2차원 배열,

a를 '1~i열을 커버하는 최소 소대원의 수',

b를 '1~i-1열과 0행 i열을 커버하는 최소 소대원의 수',

c를 '1~i-1열과 1행 i열을 커버하는 최소 소대원의 수'

라고 정의합니다.

정의상 a[0] = b[0] = c[0] = 0이며,

a[1] = (하나의 소대로 1열 2칸을 커버할 수 있으면 1, 아니면 2)

b[1] = c[1] = 1입니다.

1) b와 c

b[i] = a[i-1] + 1이며, 만약 1행의 i-1열과 i열을 한 소대가 커버할 수 있다면 b[i] = min(c[i-1] + 1, b[i])가 됩니다.

마찬가지로, c[i] =a[i-1] + 1이며, 만약 2행의 i-1열과 i열을 한 소대가 커버할 수 있다면 c[i] = min(b[i-1] + 1, c[i])입니다.

2) a

기본적으로 a[i] = min(b[i-1] + 1, c[i-1] + 1)이며,

만약 i열을 하나의 소대가 커버할 수 있다면 a[i]는 a[i-1] + 1도 가능하며,

만약 1열의 i-1, i열을 하나의 소대가 커버할 수 있고, 2열의 i-1, i열을 하나의 소대가 커버할 수 있으면 a[i]는 a[i-2] + 2도 가능합니다.

a[i]는 이 중 최솟값이 됩니다. 그리고 모든 구역을 커버하는 최소 소대 수는 a[N]이 됩니다.

 

원형을 고려하기

위 조건은 1열과 N열이 연결되어있지 않다는 전제하에 구한 소대의 최솟값입니다. 이제 1열과 N열이 연결되어 있는 경우를 고려할 필요가 있습니다. 총 3가지 경우가 있는데,

1) 1행의 1열과 1행의 N열이 한 소대로 커버됨

2) 2행의 1열과 2행의 N열이 한 소대로 커버됨

3) 1행의 1열과 1행의 N열이 한 소대로 커버되고  2행의 1열과 2행의 N열이 한 소대로 커버됨

총 네 경우로 나눌 수 있습니다. 각 경우마다, 1과 N열을 연결하는 소대는 점화식과 별개로 존재한다고 가정합시다.

각 경우마다 모양을 생각하여 a[1], b[1], c[1] 초기값을 다르게 설정합니다. 이후 점화식은 동일합니다.

그리고 초기 모양이 다르기에, 각 경우마다 최솟값을 구하는 방법이 다릅니다:

1)는 c[N] + 1

2)은 b[N]+1

3)는 a[N-1] + 2가 됩니다. 점화식에서는 1열과 N열을 연결한 소대를 고려하지 않았으므로, 1열과 N열을 연결한 소대의 수를 더해줍니다.

 

이거보다 좀더 세련된 풀이가 있을 거 같기도하고, 기대도 했는데 경우를 잘 나누는게 정답이었네요. 그와 별개로 여러 번의 수정을 거치다보니 제 코드는 꽤 깔끔합니다.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    static final int INF = 1_000_000;
    static int[] a = new int[10001], b = new int[10001], c = new int[10001];
    static int[][] e = new int[2][10001];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        tc: while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int W = Integer.parseInt(st.nextToken());
            for (int i = 0; i < 2; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 1; j <= N; j++) {
                    e[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            
            int ans = INF;
            set(N, (e[0][1] + e[1][1] <= W)? 1: 2, 1, 1);
            dp(N, W);
            ans = a[N];
            
            if (e[0][1] + e[0][N] <= W) {
                set(N, 1, 0, 1);
                dp(N, W);
                ans = Math.min(ans, c[N] + 1);
            }
            
            if (e[1][N] + e[1][1] <= W) {
                set(N, 1, 1, 0);
                dp(N, W);
                ans = Math.min(ans, b[N] + 1);
            }
            
            if (e[0][1] + e[0][N] <= W && e[1][1] + e[1][N] <= W) {
                set(N, 0, 0, 0);
                dp(N, W);
                ans = Math.min(ans, a[N-1] + 2);
            }    
            System.out.println(ans);
        }
    }
    
    static void set(int N, int a1, int b1, int c1) {
        Arrays.fill(a, 1, N+1, INF);
        Arrays.fill(b, 1, N+1, INF);
        Arrays.fill(c, 1, N+1, INF);
        a[1] = a1;
        b[1] = b1;
        c[1] = c1;
    }
    
    static void dp(int N, int W) {
        for (int i = 2; i <= N; i++) {
            b[i] = a[i-1] + 1;
            if (e[0][i-1] + e[0][i] <= W) b[i] = Math.min(b[i], c[i-1] + 1);
            
            c[i] = a[i-1] + 1;
            if (e[1][i-1] + e[1][i] <= W) c[i] = Math.min(c[i], b[i-1] + 1);
                            
            a[i] = Math.min(b[i] + 1, c[i] + 1);
            if (e[0][i] + e[1][i] <= W) 
                a[i] = Math.min(a[i], a[i-1] + 1);
            if (i>1 && e[0][i-1] + e[0][i] <= W && e[1][i-1] + e[1][i] <= W)
                a[i] = Math.min(a[i], a[i-2] + 2);
        }
    }
}