백준온라인 1006번 [습격자 초라기] [C++]

www.acmicpc.net/problem/1006

1006번: 습격자 초라기

---

문제 요약

1.길이가 N인 원형큐 2개가 인접하게 붙어있다

2.특수소대가 비용이 w보다 작게끔 하나또는 두개의  구역을 침투시킨다고 할때

3.가능한 최소의 파견 소대의 수를 출력

 

---

나의 풀이

DP문제라는것을 안 상태에서 문제를 풀었음에도 난이도가 상당했다

 

처음 원형큐를 잘라서

1 2 .......... N

1 2 ...........N 이렇게 입력으로 주어진 그대로 생각해보면 힌트를 얻을수 있다

 

입력으로 주어진 배열을 D배열이라고 하고  $D[N+1][2]$ 선언이 필요!

내가 최소의 파견횟수를 알아낼수 있는 배열을 DP배열 이라고 하자  $DP[N+1][3]$ 선언이 필요!

 

$DP[i][2]$는 다음과 같이 해석할수 있다

 

$DP[i][0]$ ==> 처음부터 i번째열의 0행  "까지만" 해결이 되었을 때의 최소의 파견횟수 

$DP[i][1]$ ==> 처음부터 i번째열의 1행  "까지만" 해결이 되었을 때의 최소의 파견횟수 

$DP[i][2]$ ==> 처음부터 i번째열의 0행,1행  "둘다" 해결이 되었을 때의 최소의 파견횟수

 

여기서 중요한건 저 DP배열의 점화식이다

 

$DP[i][0]$ 은 $DP[i-1][2]+1$ 이 기본이고

                    $D[i-1][0]+D[i][0]<=w$ 이 가능한 경우 //앞블록과 현재블록을 묶어 줄수 있는경우

                    $D[i-1][1]+1$ 둘중 작은값으로 초기화 해준다

 

$DP[i][1]$ 은 $DP[i-1][2]+1$ 이 기본이고

                    $D[i-1][1]+D[i][1]<=w$ 이 가능한 경우 //앞블록과 현재블록을 묶어 줄수 있는경우

                    $DP[i-1][0]+1$ 둘중 작은값으로 초기화 해준다

 

$DP[i][2]$ 은 우선 $minDP[i][0]+1,DP[i][1]+1$ 중 최소값으로 초기화 해주고

                    // 위의 두 식을 이용해서 구한식에 더하기 1만해서 경우의수를 일단 초기화할수 있다.

 

                     i-1열까지 완료된 경우의수 + i번째 열 0행 1행 (위 아래) 하나씩 투입을 한경우

                    $DP[i-1][2]+1$ 과   현재값중 작은값으로

 

                    $D[i][0]+D[i][1]<=w$ 이 가능한 경우  

                     $DP[i-1][2]+1$ 와 현재값중 작은값으로

                    //위 아래로 먹는게 가능한 경우

 

                    0행과 1행 모든 두 칸씩 먹는게 가능한 경우

                    $D[i][0]+D[i-1][0]<=w$  과  $D[i-1][1]+D[i][1]<=w$ 이 가능한 경우

                    $DP[i-2][2]+2$  와 현재값중 작은값으로

 

이 경우 최종적으로 답이 $DP[N][2]$ 에 담기게 된다.

 

하지만 이 경우는 1번 열에서부터 정직하게 시작한다는 것을 의미한다

이것만 살펴보게 된다면 1과 N을 묶에 주는경우를 고려 하지 못한다

 

그러면 초반에서 갈라지는 경우의 수를 판단해보면

1.1-N가 바로 만나지 않는 경우

2.$D[1][0]과D[N][0]$이 만나는 경우

3.$D[1][1]과D[N][1]$이 만나는 경우

4.$D[1][0]과D[N][0]$ 그리고$D[1][1]과D[N][1]$이 만나는 경우

 

이 네 가지 경우에 대해서 DP를 돌려주면 된다

각각 경우에 대해서는 가정에서 선택한 방을 고르지 않는 결과를 반영하여야 하는게 주의사항이다

---

코드

	#include <bits/stdc++.h>
	#define INF 0x3f3f3f3f
	#define ft first
	#define sd second
	#define all(x) (x).begin(), (x).end()
	using namespace std;
	using ll = long long;
	using pii = pair<int, int>;
	using pll = pair<ll, ll>;
	using vi = vector<int>;
	using vb = vector<bool>;
	using vs = vector<string>;
	using vd = vector<double>;
	using vll = vector<ll>;
	using vpii = vector<pii>;
	using vpll = vector<pll>;
	using vvi = vector<vi>;
	using vvb = vector<vb>;
	using vvll = vector<vll>;
	using vvpii = vector<vpii>;
	using vvpll = vector<vpll>;
	using vvs = vector<vs>;
	int d[10001][2];
	int dp[10001][3];
	void init(int n){
	for(int i=1;i<=n;i++){
	for(int j=0;j<3;j++){
	dp[i][j]=INF;
	}
	}
	}
	int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int t,n,w;
	cin>>t;
	while(t--){
	cin>>n>>w;
	for(int j=0;j<2;j++){
	for(int i=1;i<=n;i++){
	cin>>d[i][j];
	}
	}
	vi rot;
	rot.push_back(2); //첨부터쭉 끝까지
	if(d[1][0]+d[n][0]<=w)rot.push_back(1); //상단 1 n합병
	if(d[1][1]+d[n][1]<=w)rot.push_back(0); //하단 1 n합병
	if(d[1][0]+d[n][0]<=w&&d[1][1]+d[n][1]<=w)rot.push_back(-1); //둘다 합병
	int ans=INF;
	for(auto mode : rot){
	init(n);
	dp[0][0]=dp[0][1]=dp[0][2]=0;
	for(int i=1;i<=n;i++){
	if(!(i==1&&(mode==1||mode==-1))){
	dp[i][0]= min(dp[i][0],dp[i-1][2]+1);
	if(d[i-1][0]+d[i][0]<=w){
	dp[i][0]=min(dp[i][0],dp[i-1][1]+1);
	}
	}else{
	dp[i][0]=0;
	}
	if(!(i==1&&(mode==0||mode==-1))){
	dp[i][1]= min(dp[i][1],dp[i-1][2]+1);
	if(d[i-1][1]+d[i][1]<=w){
	dp[i][1]=min(dp[i][1],dp[i-1][0]+1);
	}
	}else{
	dp[i][1]=0;
	}
	if(!(i==1&&(mode==-1))){
	dp[i][2] = min({dp[i][0]+1,dp[i][1]+1,dp[i][2]});
	if(d[i][0]+d[i][1]<=w){
	dp[i][2] = min(dp[i-1][2]+1,dp[i][2]);
	}
	if(d[i-1][0]+d[i][0]<=w && d[i-1][1]+d[i][1]<=w && i-2>=0){
	dp[i][2]= min(dp[i-2][2]+2,dp[i][2]);
	}
	}else{
	dp[i][2]=0;
	}
	}
	if(mode==2)
	ans = min(ans , dp[n][2]);
	if(mode==1||mode==0)
	ans = min(ans , dp[n][mode]+1);
	if(mode==-1)
	ans = min(ans , dp[n-1][2]+2);
	}
	cout<<ans<<"\n";
	}
	}

view raw .cpp hosted with ❤ by GitHub