킹격자 갓라기
솔직히 이게 어떻게 플래3일수가 있는거지
ㅠㅠ
환형으로 입력이 주어지는데
케이스를 4가지로 나눠 생각하면 일단 입력을 2차원으로 만들 수 있다.
( 위의 사진 기준 )
1. 그 어느것도 서로 이어지지 않음.
2. 16번과 9번이 연결
3. 8번과 1번이 서로 연결
4. 16&9, 8&1이 서로 연결
이렇게 네번 계산해서 최솟값을 구해주면 되고,
이제 진짜인 DP파트다
일단 이게 디피라는건 알았으니, 디피를 해보고자 하는데
원래는 디피테이블을 dp[i][j]는 (i,j)를 출동시킬때 라고 생각하였으나
너무 복잡해 수정했다.
디피용 배열을 세개를 만드는데,
inner[k] 는 안쪽 k번이 튀어나와있는 형태로 특수소대가 배치되어있는 경우,
outer[k] 는 바깥쪽 k번이 튀어나와있는 형태로 특수소대가,
그리고 both[k]는 양쪽모두 k번까지 특수소대가 배치되는 경우의 특수소대 수이다.
이를통해 점화식을 깔끔하게 블로그로 설명하고싶었으나
수식이랑 그림 다 그리고 타이핑하기가 귀찮아서
노트에다 써놓은거 걍 찍어서 올려드리겟다
지금보니 빛반사가 심해 읽기 힘들어보이지만
소스코드에있는 내용과 별반 다를바가없다.
void fill(){
for(int i=2; i<=n; i++){
int in2 = (inarr[i-1]+inarr[i]<=w) ? 1:2;
int out2 = (outarr[i-1]+outarr[i]<=w)? 1:2;
int inout2 = (inarr[i]+outarr[i]<=w) ? 1:2;
inner[i] = min(both[i-1]+1, outer[i-1]+in2);
outer[i] = min(both[i-1]+1, inner[i-1]+out2);
both[i] = min({both[i-1]+inout2, both[i-2]+in2+out2, inner[i]+1, outer[i]+1});
}
}이렇게 점화식의 기초적인 형태를 내주었다.
참고로 i가 2부터 시작하는이유는
both[i]의 계산과정에서 세그폴트가 발생하지 않게 하기 위함이다.
덕분에 모든 dp배열의 1번 인덱스를
수동으로 넣어줘야했다 ㅠ
양쪽 모두 연결되지 않는 기본케이스다.
// 양쪽 모두 연결되지 않음 //
inner[1] = outer[1] = 1;
both[1] = (inarr[1]+outarr[1]<=w) ? 1:2;
fill();
ans = min(ans, both[n]);
clear();both[1]의 경우
[] 모양의 가로로 긴 블록이 배치될 수도 있기때문에, 저렇게 표현해주었다.
fill()함수는 디피테이블에 따라 쭉 까는함수고
clear()는 배열초기화다.
// 안쪽 연결됨 //
if(n!=1 && inarr[1]+inarr[n] <= w){
inner[1] = outer[1] = 1; both[1] = 2;
inarr[1] = INF;
fill();
ans = min(ans, outer[n]);
inarr[1] = tmpin;
clear();
}inarr[1]에서 입력값을 큰 값으로 바꿔주면, 해당 위치를 사용하는 값들은
절대로 최솟값이 될 수 없다. 그렇기에 inarr[1]을 통해서
위치를 이미 사용한거같은 효과를 낼 수 있다.
inarr[1]의 값을 다시 돌리기 위해 tmpin이라는 변수를 만들어 다시 대입해준 모습이다.
전체 소스코드는
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <string.h>
#define INF 9999999
using namespace std;
int n,w;
int inner[12345];
int outer[12345];
int both[12345];
int inarr[12345];
int outarr[12345];
int tmpin;
int tmpout;
void clear(){
memset(inner, 0, sizeof(inner));
memset(outer, 0, sizeof(outer));
memset(both, 0, sizeof(both));
}
void fill(){
for(int i=2; i<=n; i++){
int in2 = (inarr[i-1]+inarr[i]<=w) ? 1:2;
int out2 = (outarr[i-1]+outarr[i]<=w)? 1:2;
int inout2 = (inarr[i]+outarr[i]<=w) ? 1:2;
inner[i] = min(both[i-1]+1, outer[i-1]+in2);
outer[i] = min(both[i-1]+1, inner[i-1]+out2);
both[i] = min({both[i-1]+inout2, both[i-2]+in2+out2, inner[i]+1, outer[i]+1});
}
}
int main(){
int t;
scanf("%d", &t);
while(t--){
int ans = INF;
scanf("%d %d", &n, &w);
for(int i=1; i<=n; i++) scanf("%d", &inarr[i]);
for(int i=1; i<=n; i++) scanf("%d", &outarr[i]);
tmpin = inarr[1];
tmpout = outarr[1];
// 양쪽 모두 연결되지 않음 //
inner[1] = outer[1] = 1;
both[1] = (inarr[1]+outarr[1]<=w) ? 1:2;
fill();
ans = min(ans, both[n]);
clear();
// 안쪽 연결됨 //
if(n!=1 && inarr[1]+inarr[n] <= w){
inner[1] = outer[1] = 1; both[1] = 2;
inarr[1] = INF;
fill();
ans = min(ans, outer[n]);
inarr[1] = tmpin;
clear();
}
// 바깥쪽 연결됨 //
if(n!=1 && outarr[1]+outarr[n] <= w){
inner[1] = outer[1] = 1; both[1] = 2;
outarr[1] = INF;
fill();
ans = min(ans, inner[n]);
outarr[1] = tmpout;
clear();
}
// 양쪽 둘다 연결됨 //
if(n!=1 && inarr[1]+inarr[n]<=w && outarr[1]+outarr[n]<=w){
inner[1] = outer[1] = 1; both[1] = 2;
inarr[1] = outarr[1] = INF;
fill();
ans = min(ans, both[n-1]);
inarr[1] = tmpin;
outarr[1] = tmpout;
clear();
}
printf("%d\n", ans);
}
return 0;
}매우 끔찍하게 길다.
맞왜틀 엄청심해서
오늘 하루종일풀었다.
역시 킹격자 갓라기.... 이겼지만 강력한 상대였다!
윤님 제작의 이모티콘과 함께 글을 마치겠다 ^^7
+ 네이버블로그 글 옮기느라
시간순이 좀 엉망진창인데
현재 코더의 티어는
요정도쯤 된다.