[PS] BOJ 1006습격자 초라기

DFS + memorized 방법으로 풀면 쉽다.

원형으로 된 배열을 처음과 끝을 분리하여 선형구조로 풀고,

지그재그 형태로 순서를 명시하고 각 원소에 해당되는 최소값을 table에 저장하여 memorized로
풀면 된다.

첫 열에 대해 4가지 경우를 모두 풀면 된다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
const int INF = 99999999;
using namespace std;
int arr[2][10010];
int dp[2][10010];
int T, N, W, A;
int DFS(int i, int j) {
    if (j >= N)return 0;
    int& r = dp[i][j];
    int k = abs(i - 1);
    if (r!=-1)return r;
    if (j == N - 1){
        if (i){
            return 1;
        }
        else{
            if (arr[0][j] + arr[1][j] <= W){
                return 1;
            }
            return 2;
        }
        return i ? 1 : 1 + (arr[0][j] + arr[1][j] > W);

    }
    r = INF;
    if (i==0 && arr[0][j] + arr[1][j] <= W){
        r = min(r, DFS(0, j + 1) + 1);
    }
    if (arr[i][j] + arr[i][j + 1] <= W){
        if (arr[k][i + j] + arr[k][i + j + 1] <= W){
            r = min(r, DFS(i, j + 2) + 2);
        }
        r = min(r, DFS(k,i + j + 1) + 2);
    }
    r = min(r, DFS(k,i+j) + 1);
    return r;
}
int main() {
    cin >> T;
    while (T--){
        cin >> N >> W;
        generate(arr[0], arr[0] + N, []()->int{int i; cin >> i; return i; });
        generate(arr[1], arr[1] + N, []()->int{int i; cin >> i; return i; });
        fill(dp[0],dp[0]+N, -1);
        fill(dp[1], dp[1] + N, -1);
        A = INF;
        A = min(A,DFS(0, 0));
        int a = arr[0][0];
        int b = arr[0][N-1];
        int c = arr[1][0];
        int d = arr[1][N-1];
        if (N != 1){
            if (a + b <= W && c + d <= W){
                fill(dp[0], dp[0] + N, -1);
                fill(dp[1], dp[1] + N, -1);
                arr[0][0] = arr[0][N - 1] = arr[1][0] = arr[1][N - 1] = INF;
                A = min(A, DFS(0, 0) - 2);
                arr[0][0] = a;
                arr[0][N - 1] = b;
                arr[1][0] = c;
                arr[1][N - 1] = d;
            }
            if (a + b <= W){
                fill(dp[0], dp[0] + N, -1);
                fill(dp[1], dp[1] + N, -1);
                arr[0][0] = arr[0][N - 1] = INF;
                A = min(A, DFS(0, 0) - 1);
                arr[0][0] = a;
                arr[0][N - 1] = b;
            }
            if (c + d <= W){
                fill(dp[0], dp[0] + N, -1);
                fill(dp[1], dp[1] + N, -1);
                arr[1][0] = arr[1][N - 1] = INF;
                A = min(A, DFS(0, 0) - 1);
            }
        }
        cout << A << endl;
    }
}