[백준] 1006 - 습격자 초라기 (c++)

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

 

문제 요약

그림과 같은 두줄짜리 환형 건물이 있다. 각 구역마다 배치된 적의 수가 주어진다.

구역마다 소대를 침투시킬 것이다. 한 소대엔 w명이 있고 두 구역 적의 수 합이 w보다 작거나 같으면 인접한 두 구역까지 침투할 수 있다. 모든 구역에 소대를 침투시키기 위해 필요한 최소 소대 수를 구해라.

풀이 (N)

• DP

환형을 처리하는게 정말 까다로운 문제였다. 일단 선형 문제라 생각하고 풀어보자. dp[n][3]  dp[i][j] = i-1까지 모두 커버 했고 i의 상태가 j일때 최소 소대 수 라고 정의하고 채워주면 어렵지 않게 풀 수 있다. 1열과 n열을 잇는 경우의 수를 모두 base case로 만들어 한 번씩 돌려보면 환형 문제를 해결할 수 있다.

 

base case를 엄청 꼼꼼히 채워야 한다. 틀릴 수 있는 경로가 굉장히 많다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mid (st+en>>1)

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;cin>> t;
    while(t--) {
        int n,w;cin>>n>>w;
        vector<array<int,2>> ar(n);
        for(auto&x:ar) 
            cin>>x[0];
        for(auto&x:ar)
            cin>>x[1];
        ar.insert(ar.begin(),{0,0});
    
        vector<vector<int>> dp(n+1,vector<int>(3,1e9)); //0둘다, 1위만, 2아래만
        auto Up = [&](){
            for(int i=2;i<=n;i++) { 
                int ver=(ar[i][0]+ar[i][1]<=w?1:2),top=(ar[i-1][0]+ar[i][0]<=w?1:2),bot=(ar[i-1][1]+ar[i][1]<=w?1:2);
                dp[i][0]=min({dp[i-1][0]+ver,dp[i-1][1]+bot+1,dp[i-1][2]+top+1,dp[i-2][0]+top+bot});
                dp[i][1]=min({dp[i-1][2]+top,dp[i-1][0]+1});
                dp[i][2]=min({dp[i-1][1]+bot,dp[i-1][0]+1});
            }
        };

        dp[0][0]=0;     //그냥 시작 
        dp[1][1]=dp[1][2]=1;
        dp[1][0]=(ar[1][0]+ar[1][1]<=w?1:2);
        Up();
        int ans=dp[n][0];

        for(auto&x:dp)          //둘다  
            fill(x.begin(),x.end(),1e9);
        dp[1][0]=(ar[1][0]+ar[n][0]<=w?1:2)+(ar[1][1]+ar[n][1]<=w?1:2);
        Up();
        ans=min(ans,dp[n-1][0]);

        for(auto&x:dp)          //위    
            fill(x.begin(),x.end(),1e9);
        dp[1][1]=(ar[1][0]+ar[n][0]<=w?1:2);
        dp[1][0]=dp[1][1]+1;
        Up();
        ans=min(ans,dp[n][2]);

        for(auto&x:dp)      //아래  
            fill(x.begin(),x.end(),1e9);
        dp[1][2]=(ar[1][1]+ar[n][1]<=w?1:2);
        dp[1][0]=dp[1][2]+1;
        Up();
        ans=min(ans,dp[n][1]);

        cout<<ans<<'\n';
    }
}