https://www.acmicpc.net/problem/1006
습격자 초라기 문제..백준 온라인 문제 번호 순서대로 푸는 사람들이 포기하기 시작하는 1006번 문제 DP 문제이다. 어렵다. 기본적인 알고리즘 어느정도 떠오르기는 했는데. 여러가지의 경우의 수를 정리해서 점화식으로 정리하는게 명확하게 안떠올라 답을 봤음….
우선 연결된 도넛 모양의 구역을 펼쳐서 2개의 행을 가진 직사각형으로 생각을 해본다. 그리고 i-1 열까지 채우는 경우, i-1 열까지 채우고 i의 1행을 채우는 경우, i-1 열까지 채우고 i의 2행을 채우는 경우 새가지의 경우로 나누어서 생각을 해본다. 각각의 경우는 a[i], b[i], c[i] 배열로 처리를 한다.
i열까지 채우는 방법의 최소 갯수는 위의 세가지 경우에 i열에서 남아있는 빈 구역을 채우는 방법의 갯수를 추가하여 그 중에 최소값을 구하면 된다. 그 방법은 아래와 같이 네가지의 경우로 나눌 수 있다.
- i-1열까지 다 채우고 1행 2행 (두행의 합이 W 보다 작을때)을 겹쳐서 1개 놓았을때.
- i-2열까지 다 채우고 1행 i-1~i열, 2행 i-1~ i열을 각각 1개씩 2개를 겹쳐 놓았을때.
- i-1 열까지 다채우고 i의 1행을 채우는 경우에 2행에 1개를 추가하여 놓았을때.
- i-1 열까지 다채우고 i의 2행을 채우는 경우에 1행에 1개를 추가하여 놓았을때.
이렇게 생각하면 i-1까지 다 채우고 i열에 1행에 1개 2행에 1개 씩 놓는 경우가 빠진것 처럼 생각이 드는데 그 경우는 3번, 4번의 경우를 생각할때 고려가 되어서 계산이 된다. 위의 4개의 경우를 점화식으로 구성하면 아래와 같이 된다.
a[i+1] = min(b[i]+1, c[i]+1); // 3,4번의 경우 중 최소값.
//i열까지 1행을 채우는 경우에 1(2행 1구역)을 더한 값과 i열까지 2행을 채우는 경우에 1을 더한 값 중에 최소값.
if (e[i][0] + e[i][1] <= W) { //
a[i+1] = min(a[i+1], a[i]+1); //1번 경우. i-1열까지 채우고 i열의 1행, 2행 합이 W값 보다 작아서 1개로
//겹쳐 놓았을 경우.
}
if(i > 0 && e[i-1][0]+e[i][0] <= W && e[i-1][1]+e[i][1] <= W ) {
a[i+1] = min(a[i+1], a[i-1] + 2); // 2번 경우. i-2열까지 채우고 1행의 i-1~i까지 1개,
// 2행의 i-1~i까지 1개. 총 2개를 겹쳐서 놓을 경우.
}
위와 같이 점화식이 구성된다.
b[i], c[i] 아래와 같이 점화식이 구성된다.
b[i] = a[i] + 1; // a[i]는 i-1열까지 채운 갯수. 여기에 1행에 1칸 채운 경우.
if(e[i-1][0]+ e[i][0] <= W) { // 1행의 i열 과 i-1의 합이 W보다 적어서 한개로 두칸 채울 경우
b[i] = min(b[i] ,c[i-1] + 1); //c[i-1]은 i-2까지 채우고 2행 1칸 채운 경우에
//한개로 1행 두칸 채운 경우 더함. 그리고 기존 경우와 비교해서 최소 값을 저장.
}
c[i] = a[i]+1; // 2행의 경우로 위의 경우 반대로 생각하면 됨.
if(e[i-1][1]+ e[i][1] <= W) {
c[i] = min(c[i] ,b[i-1] + 1);
}
i의 범위는 0~N-1 부터 이다. a[0] 는 -1 열까지 채운 부대의 갯수 이므로 0. b[0], c[0] 는 -1열 까지 가득 채우고 0열에 1개의 행만 채운 경우 이므로 1이다.
위까지의 경우는 환형을 직사각형으로 펼친 경우를 고려한 것이고, 이 경우는 N-1열까지 빈칸없이 배치가 되었다는 것으로 볼수 있다. 환형으로 고려 할 경우에는 N-1 열과 0열 간의 겹치는 경우를 고려해야 한다. 그 경우는 아래와 같다.
- N-1열의 1행 과 0 열의 1행을 겹쳐서 놓을 경우.
- N-1열의 2행 과 0 열의 2행을 겹쳐서 놓을 경우.
- N-1열의 1행, 2행을 0을 과 모두 겹친 경우.
위의 세가지의 경우 마다 각각 다른 초기값이 설정 되며. 그 초기값으로 설정후 다시 위의 점화식을 수행하여 계산하고 비교 해야 한다. 위의 경우에는 0열이 없어진다고 생각하고, 0열의 경우가 1열에 값 a[1], b[1], c[1] 에 반영되어 계산을 수행 하면된다.
-
a[1] 은 0열까지 가득 채울 경우의 수이므로 1 이된다. b[1] 은 1열에 1행까지 채울 경우의 수이므로 2가 된다. c[1] 은 1열에 2행까지 채울 경우의 수인데 0열의 2행과 1열의 2행의 합이 W보다 적으면 1개로 놓을 수 있으므로 1. 그렇지 않을 경우는 2개를 놓아야 함으로 2가 된다. 이 경우에 계산 되는 최소값은 c[N-1] +1이 된다.
-
a[1] 은 0열까지 가득 채울 경우의 수이므로 1 이된다. b[1] 은 1열에 2행까지 채울 경우의 수인데 0열의 2행과 1열의 2행의 합이 W보다 적으면 1개로 놓을 수 있으므로 1. 그렇지 않을 경우는 2개를 놓아야 함으로 2가 된다. c[1] 은 1열에 2행까지 채울 경우의 수이므로 2가 된다. 이 경우에 계산 되는 최소값은 b[N-1] +1이 된다.
-
0까지 가득 채워지게 됨으로 a[1] 은 0 b[1] 은 c[1] 1이 된다. 이 경우에 계산 되는 최소값은 a[N-1] + 2 가 된다.
최종 소스는 아래와 같다.
#include "bits/stdc++.h"
using namespace std;
int a[18181];
int b[18181];
int c[18181];
int e[18181][2];
int N,W;
void solve(int start) {
for(int i = start; i < N;i++) {
a[i+1] = min(b[i]+1,c[i]+1);
if((e[i][0]+e[i][1]) <= W){
a[i+1] = min(a[i+1],a[i]+1);
}
if(i > 0 && e[i-1][0]+e[i][0] <= W && e[i-1][1]+e[i][1] <= W){
a[i+1] = min(a[i+1],a[i-1]+2);
}
if(i < N-1) {
b[i+1] = a[i+1] + 1;
if((e[i+1][0] + e[i][0] <= W)) {
b[i+1] = min(b[i+1],c[i]+1);
}
c[i+1] = a[i+1] + 1;
if((e[i+1][1] + e[i][1] <= W)) {
c[i+1] = min(c[i+1],b[i]+1);
}
}
}
}
int res;
int main(int argc, const char * argv[]) {
// insert code here...
int T;
scanf("%d",&T);
for(int t = 0; t < T;t++) {
scanf("%d%d",&N,&W);
for(int i = 0 ; i < N; i++)
scanf("%d",&e[i][0]);
for(int i = 0 ; i < N; i++)
scanf("%d",&e[i][1]);
a[0] = 0;
b[0] = c[0] = 1;
res = 30000;
solve(0);
res = min(res, a[N]);
if(N > 1 && e[0][0] + e[N-1][0] <= W) {
b[1] = 2;
a[1] = 1;
c[1] = e[0][1] + e[1][1] <= W ? 1 : 2;
solve(1);
res = min(res,c[N-1] + 1);
}
if(N > 1 && e[0][1] + e[N-1][1] <= W) {
b[1] = e[0][0] + e[1][0] <= W ? 1 : 2;
a[1] = 1;
c[1] = 2;
solve(1);
res = min(res,b[N-1] + 1);
}
if(N > 1 && e[0][1] + e[N-1][1] <= W && e[0][0] + e[N-1][0] <= W) {
b[1] = 1;
a[1] = 0;
c[1] = 1;
solve(1);
res = min(res,a[N-1] + 2);
}
printf("%d\n",res);
}
return 0;
}