#include #include using namespace std; const int INF = 987654321; int T, N, W; int map[10001][2]; //0~N-1 int cache[10001][5];//1~N i줄까지 채움, 상태 s int solve(int p, int s, int cir){ int& ret = cache[p][s]; if(ret != INF) return ret; if(p == N){ ret = 0; return ret; }else if(p == N - 1){ if(cir == 3){ ret = 0; }else if(cir == 2 && s == 2){ ret = 0; }else if(cir == 1 && s == 1){ ret = 0; }else if(cir == 0 && s == 0){ ret = (map[p][0] + map[p][1]) <= W ? 1 : 2; }else{ ret = 1; } return ret; }// 기저 조건 : 마지막 2칸 제외한 모든 칸이 채워졌을 때 if(s == 0 && (map[p][0] + map[p][1]) <= W){ int cur = solve(p + 1, 0, cir) + 1; ret = min(ret, cur); } // 위, 아래 1칸씩 채우기 if(s != 3){ int cur; if(s == 0){ cur = solve(p, 1, cir) + 1; }else if(s == 1){ cur = solve(p, 3, cir) + 1; }else if(s == 2){ cur = solve(p + 1, 0, cir) + 1; }else if(s == 4){ cur = solve(p + 1, 2, cir) + 1; } ret = min(ret, cur); } //윗줄 1칸 채우기 if(s != 4){ int cur; if(s == 0){ cur = solve(p, 2, cir) + 1; }else if(s == 1){ cur = solve(p + 1, 0, cir) + 1; }else if(s == 2){ cur = solve(p, 4, cir) + 1; }else if(s == 3){ cur = solve(p + 1, 1, cir) + 1; } ret = min(ret, cur); } //아래줄 1칸 채우기 if((s % 2) == 0 && (map[p][0] + map[p + 1][0]) <= W){ int cur; if(s == 0){ cur = solve(p, 3, cir) + 1; }else if(s == 2){ cur = solve(p + 1, 1, cir) + 1; }else{ cur = solve(p + 2, 0, cir) + 1; } ret = min(ret, cur); } //윗줄 2칸 채우기 if(((s % 2) == 1 || s == 0) && (map[p][1] + map[p + 1][1] <= W)){ int cur; if(s == 0){ cur = solve(p, 4, cir) + 1; }else if(s == 1){ cur = solve(p + 1, 2, cir) + 1; }else{ cur = solve(p + 2, 0, cir) + 1; } ret = min(ret, cur); } //아래줄 2칸 채우기 return ret; } int main() { cin>>T; for(int c = 0; c < T; c++){ cin>>N>>W; fill(map[0], map[10000] + 2, 0); fill(cache[0], cache[10000] + 16, INF); for(int i = 0; i < 2; i++){ for(int j = 0; j < N; j++){ cin>>map[j][i]; } } if(N == 1){ if(map[0][0] + map[0][1] <= W){ cout<<1<

제출 #56360

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: