문제 태그 : https://www.acmicpc.net/problem/1006
앞에서 순서대로 푸는 사람들이 절망할만한 문제이다. 1000~1005 보단 확실히 난이도가 있다.
문제 설명
원형 2열로 배치된 2n 개의 칸을 최소 그룹의 갯수로 묶어야 한다. 그룹에는 조건이 있다. 최대 2개가 같은 그룹일 수 있으며, 배치 상에서 연속된 칸이어야 하고, 두 칸의 값의 합이 m을 넘지 않아야 한다.
2칸이 한 줄이고 n줄이 있다고 생각하면 된다.
문제 풀이
DP를 쓰고 싶은 느낌이 들었다. 어떤 줄까지 다 채우는데 사용된 최소 그룹의 갯수를 이용해 다음 줄까지 채우는데 사용된 최소 그룹의 갯수에 영향을 준다고 생각할 수 있기 때문이다. 하지만 문제가 있다. 어떤 칸을 채울 때에는 이전 칸을 완벽히 채운 상황만 고려해서는 최적의 결과를 얻어낼 수 없다. 왜냐하면 이전칸과 같이 한 그룹을 만들어야 할 상황도 있기 때문이다. 일단 dp[i]은 i번째 줄까지 채우는데 사용된 최소 그룹의 갯수라고 정의하자.
위에서 언급한 문제점을 해결 하기 위해서 모든 경우의 수를 다 따져주면 된다. 어떤 줄의 칸을 모두 채우는 경우만 따지지 말고, 그 줄의 윗칸 까지만 채웠을 때, 아랫칸 까지만 채웠을 때, 두 칸 모두 채웠을 때의 경우의 수를 모두 저장하자.
어떤 줄의 아랫칸만 채울 때 까지의 값(최소 그룹수) 는 전 줄의 윗칸까지만 채웠을 때 +2 or +1 이다. 이런 식으로 각 상황은 전 상황의 어떤 상황에서 영향을 받을 지 생각하여 식을 세우면 된다.
이 문제에서 요구하는 바는 하나가 더 있다. 바로 직사각형이 아니라 원형이라는 것이다. 따라서 이를 직사각형에서 생각할 때는 첫 줄과 마지막 줄 사이의 한 그룹도 고려를 해주어야 한다. 이에 따른 경우의 수는 총 4가지가 될 것이다.
i) 둘을 연결한 그룹이 없을 경우 ii) 윗칸만 연결 된 경우 iii) 아랫칸만 연결 된 경우 iiii) 둘 다 연결 된 경우
이렇게 4가지에 대해서 모두 돌려줘도 상수이므로 한 케이스당 O(N) 총 O(TN)으로 해결이 가능하다.
여담
DP에서 강조하는 어떤 값을 구하기 위한 그 세부 문제에 대한 정답을 확실히 알고 그 관계도 확실해야한다. 이 말을 지키기 위해서 할 수 있는 여러가지 방법 중 경우의 수로 쪼개는 방식으로 푸는 문제였다. 위의 풀이를 보면 알 수 있듯이 계속 반복되는 과정이라 코드도 반복이 엄청 많고 길다.
구현
예외 처리를 조심해야 한다. 나는 4가지 시작-끝을 고려하는 것을 맨 첫 줄에서 칸을 때서 마지막 칸 뒤에 붙이는 것으로 처리를 해주었다. 이때 2번째 줄을 채울 때 불가능한 경우에서 오지 않도록 조심을 해주었다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
ll t;
scanf("%lld",&t);
while(t--){
ll i,j,k,l,m,n;
ll dp[4][4][10101];
ll arr[2][10101];
for(i=0;i<4;i++){
for(j=0;j<4;j++){
for(k=1;k<=10100;k++){
dp[i][j][k]=1e18;
}
}
}
scanf("%lld %lld",&n,&m);
for(i=1;i<=n;i++)
scanf("%lld",&arr[0][i]);
for(i=1;i<=n;i++)
scanf("%lld",&arr[1][i]);
arr[0][n+1]=arr[0][1];
arr[1][n+1]=arr[1][1];
if(n==1){
if(arr[0][1]+arr[1][1]<=m) printf("1\n");
else printf("2\n");
continue;
}
dp[0][1][1]=1;
dp[0][2][1]=1;
if(arr[0][1]+arr[1][1]<=m) dp[0][3][1]=1;
else dp[0][3][1]=2;
for(i=2;i<=n;i++){
dp[0][1][i]=min(dp[0][1][i],dp[0][3][i-1]+1);
if(arr[0][i-1]+arr[0][i]<=m) dp[0][1][i]=min(dp[0][1][i],dp[0][2][i-1]+1);
dp[0][2][i]=min(dp[0][2][i],dp[0][3][i-1]+1);
if(arr[1][i-1]+arr[1][i]<=m) dp[0][2][i]=min(dp[0][2][i],dp[0][1][i-1]+1);
dp[0][3][i]=min(dp[0][3][i],dp[0][3][i-1]+2);
if(arr[0][i]+arr[1][i]<=m) dp[0][3][i]=min(dp[0][3][i],dp[0][3][i-1]+1);
if(arr[0][i-1]+arr[0][i]<=m) dp[0][3][i]=min(dp[0][3][i],dp[0][2][i-1]+2);
if(arr[1][i-1]+arr[1][i]<=m) dp[0][3][i]=min(dp[0][3][i],dp[0][1][i-1]+2);
if(arr[1][i-1]+arr[1][i]<=m&&arr[0][i-1]+arr[0][i]<=m) dp[0][3][i]=min(dp[0][3][i],dp[0][3][i-2]+2);
}
dp[1][2][1]=1;
dp[1][1][2]=2;
dp[1][2][2]=2;
if(arr[1][2]+arr[1][1]<=m){
dp[1][2][2]=1;
dp[1][3][2]=2;
}
if(arr[1][2]+arr[0][2]<=m){
dp[1][3][2]=2;
}
dp[1][3][2]=min(dp[1][3][2],(ll)3);
k=1;
for(i=3;i<=n+1;i++){
dp[k][1][i]=min(dp[k][1][i],dp[k][3][i-1]+1);
if(arr[0][i-1]+arr[0][i]<=m) dp[k][1][i]=min(dp[k][1][i],dp[k][2][i-1]+1);
dp[k][2][i]=min(dp[k][2][i],dp[k][3][i-1]+1);
if(arr[1][i-1]+arr[1][i]<=m) dp[k][2][i]=min(dp[k][2][i],dp[k][1][i-1]+1);
dp[k][3][i]=min(dp[k][3][i],dp[k][3][i-1]+2);
if(arr[0][i]+arr[1][i]<=m) dp[k][3][i]=min(dp[k][3][i],dp[k][3][i-1]+1);
if(arr[0][i-1]+arr[0][i]<=m) dp[k][3][i]=min(dp[k][3][i],dp[k][2][i-1]+2);
if(arr[1][i-1]+arr[1][i]<=m) dp[k][3][i]=min(dp[k][3][i],dp[k][1][i-1]+2);
if(arr[1][i-1]+arr[1][i]<=m&&arr[0][i-1]+arr[0][i]<=m) dp[k][3][i]=min(dp[k][3][i],dp[k][3][i-2]+2);
}
dp[2][1][1]=1;
dp[2][2][2]=2;
dp[2][1][2]=2;
if(arr[0][2]+arr[0][1]<=m){
dp[2][1][2]=1;
dp[2][3][2]=2;
}
if(arr[1][2]+arr[0][2]<=m){
dp[2][3][2]=2;
}
dp[2][3][2]=min(dp[2][3][2],(ll)3);
k=2;
for(i=3;i<=n+1;i++){
dp[k][1][i]=min(dp[k][1][i],dp[k][3][i-1]+1);
if(arr[0][i-1]+arr[0][i]<=m) dp[k][1][i]=min(dp[k][1][i],dp[k][2][i-1]+1);
dp[k][2][i]=min(dp[k][2][i],dp[k][3][i-1]+1);
if(arr[1][i-1]+arr[1][i]<=m) dp[k][2][i]=min(dp[k][2][i],dp[k][1][i-1]+1);
dp[k][3][i]=min(dp[k][3][i],dp[k][3][i-1]+2);
if(arr[0][i]+arr[1][i]<=m) dp[k][3][i]=min(dp[k][3][i],dp[k][3][i-1]+1);
if(arr[0][i-1]+arr[0][i]<=m) dp[k][3][i]=min(dp[k][3][i],dp[k][2][i-1]+2);
if(arr[1][i-1]+arr[1][i]<=m) dp[k][3][i]=min(dp[k][3][i],dp[k][1][i-1]+2);
if(arr[1][i-1]+arr[1][i]<=m&&arr[0][i-1]+arr[0][i]<=m) dp[k][3][i]=min(dp[k][3][i],dp[k][3][i-2]+2);
}
dp[3][1][2]=1;
dp[3][2][2]=1;
if(arr[0][2]+arr[1][2]<=m) dp[3][3][2]=1;
else dp[3][3][2]=2;
k=3;
for(i=3;i<=n+1;i++){
dp[k][1][i]=min(dp[k][1][i],dp[k][3][i-1]+1);
if(arr[0][i-1]+arr[0][i]<=m) dp[k][1][i]=min(dp[k][1][i],dp[k][2][i-1]+1);
dp[k][2][i]=min(dp[k][2][i],dp[k][3][i-1]+1);
if(arr[1][i-1]+arr[1][i]<=m) dp[k][2][i]=min(dp[k][2][i],dp[k][1][i-1]+1);
dp[k][3][i]=min(dp[k][3][i],dp[k][3][i-1]+2);
if(arr[0][i]+arr[1][i]<=m) dp[k][3][i]=min(dp[k][3][i],dp[k][3][i-1]+1);
if(arr[0][i-1]+arr[0][i]<=m) dp[k][3][i]=min(dp[k][3][i],dp[k][2][i-1]+2);
if(arr[1][i-1]+arr[1][i]<=m) dp[k][3][i]=min(dp[k][3][i],dp[k][1][i-1]+2);
if(arr[1][i-1]+arr[1][i]<=m&&arr[0][i-1]+arr[0][i]<=m) dp[k][3][i]=min(dp[k][3][i],dp[k][3][i-2]+2);
}
printf("%lld\n",min({dp[0][3][n],dp[3][3][n+1],dp[1][1][n+1],dp[2][2][n+1]}));
}
}
|
cs |
'코딩 > 백준 문제 풀이' 카테고리의 다른 글
| BOJ 18292 - NM과 K (2) (0) | 2020.02.29 |
|---|---|
| BOJ 17955 - Max or Min (0) | 2020.02.17 |
| BOJ 1520 - 내리막 길 (0) | 2020.01.24 |
| BOJ 4243 - 보안 업체 (0) | 2019.12.03 |
| BOJ 1848 - 동굴 탐험 (0) | 2019.11.25 |