문제
https://www.acmicpc.net/problem/1006
풀이
이것도 보고 풀었다. 며칠간 고민해봤는데, 처음에는 그래프로 크기가 큰 값 혹은 지역 번호가 큰 값에서 아래로 떨어지듯이 단방향 그래프를 그려서 하면 사이클이 없으니 dp를 적용할 수 있지 않을까~~~ 생각이 들어서 해봤는데 이게 반례가 너무 명확하게 있었다. (사실 dp도 아니고 dfs에 가깝긴 했다)
그래서 어떻게 dp를 적용해야지 하고 며칠간 고민하다가 답이 안나와서 풀이를 슬쩍 봤더니 이게 타일링으로 푸는 문제라더라...
그거 보고 머리가 띵 했다. 요새 기본으로 풀 생각을 안하고 얍샙이로 푸는 습관을 들여서 그런가 dp를 안풀어서 그런가...
그래서 타일링으로 진행하려는데 나같은 경우에는 위아래 모두 채울때 1개짜리 2개, 가로로 2개, 세로 1개 해서 4개, 위, 아래는 각각 가로 1개 1개까지 1개해서 총 8가지의 경우의 수가 나왔다. 다만 이렇게 하면 한쪽 짜리가 먼저 계산이 되어야 양쪽 짜리를 계산할 수 있기 때문에 그 점을 유의하자.
그렇게 하고 보니까 이게 원형 dp라더라 이걸 어떻게 풀까 고민을 하고 그냥 이어주는 식으로 dp를 돌리면 되지 않을까~~ 해서 대충 돌렸더니 안풀렸다. 내가하는 식으로 하면 이미 이어져있는지 안이어져있는지 몰라서 안되더라.(dp 1이 다른 값이랑 이어진 결과인지 아닌지)
또 그래서 다른 사람껄 봤더니 area 값을 W이상의 값(INF)로 바꿔서 다른 거랑 이어지지 못하게 확정한 다음에 4가지 (양쪽, 한쪽 2개, 안이어짐)해서 dp돌려서 풀더라.
그렇게 하고 n == 1일때 이어지지 못하는 예외처리, 전에 이상한 초기화 때문에 0번이 INF로 초기화 되어있었는데 이거 0으로 초기화해야 제대로 돌아간다. 그렇게 하니까 풀리더라
dp 골드 ~ 플레 문제 10문제 정도만 풀어봐야 겠다. 요새 그래프만 너무 푼 것 같다.
화이팅
실수
- 문제가 입력이 뭔가 이상하게 주어졌다면 내가 이상한건 아닌지 생각해봅시다.
- 쉽고 간단한 풀이를 생각해 봅시다.
- 알고리즘에 기반하여 먼저 생각해 봅시다.
- 초기화, corner case를 잘 생각합시다.
코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
vector<int> area(21000, 2e9);
vector<vector<int>> dp(21000, vector<int>(3, 2e9)); // 0 위아래 모두 채구기, 1 아래만 채우기, 2 위만 채우기
int N, W;
int res;
void solve() {
// 초기화
fill_n(dp.begin(), 2 * N + 1, vector<int>(3, 2e9));
if (area[1] + area[1 + N] <= W) // 세로로 세울 수 있을 때
dp[1][0] = 1;
else
dp[1][0] = 2; // 없을 때
dp[1][1] = 1;
dp[1][2] = 1;
dp[0][0] = 0;
for (int j = 2; j <= N; j++) {
// 아래쪽 만
dp[j][1] = min(dp[j][1], dp[j - 1][0] + 1);
if (area[j] + area[j - 1] <= W)
dp[j][1] = min(dp[j][1], dp[j - 1][2] + 1);
// 위쪽 만
dp[j][2] = min(dp[j][2], dp[j - 1][0] + 1);
if (area[j + N] + area[j - 1 + N] <= W)
dp[j][2] = min(dp[j][2], dp[j - 1][1] + 1);
// 양쪽 채우기
dp[j][0] = min(dp[j][0], dp[j][1] + 1);
dp[j][0] = min(dp[j][0], dp[j][2] + 1);
if (area[j] + area[j + N] <= W)
dp[j][0] = min(dp[j][0], dp[j - 1][0] + 1);
if (area[j] + area[j - 1] <= W && area[j + N] + area[j - 1 + N] <= W)
dp[j][0] = min(dp[j][0], dp[j - 2][0] + 2);
}
}
int main() {
int t;
scanf("%d", &t);
for (int i = 0; i < t; i++) {
scanf("%d %d", &N, &W);
for (int j = 1; j <= 2 * N; j++) {
scanf(" %d", &area[j]);
}
res = 2e9;
// 이어지는게 없다고 가정
solve();
res = min(res, dp[N][0]);
// 이어지는게 아래로 하나 있다고 가정
if (N != 1) {
if (area[1] + area[N] <= W) {
int temp1;
int temp2;
temp1 = area[1];
temp2 = area[N];
area[1] = W;
area[N] = W;
solve();
dp[N][0] = min(dp[N][2], dp[N][0]);
res = min(res, dp[N][0]);
area[1] = temp1;
area[N] = temp2;
}
// 이어지는게 위로 하나 있다고 가정
if (area[1 + N] + area[N + N] <= W) {
int temp1;
int temp2;
temp1 = area[1 + N];
temp2 = area[N + N];
area[1 + N] = W;
area[N + N] = W;
solve();
dp[N][0] = min(dp[N][1], dp[N][0]);
res = min(res, dp[N][0]);
area[1 + N] = temp1;
area[N + N] = temp2;
}
// 이어지는게 두개 있다고 가정
if (area[1] + area[N] <= W && area[1 + N] + area[N + N] <= W) {
int temp1;
int temp2;
int temp3;
int temp4;
temp1 = area[1];
temp2 = area[N];
temp3 = area[1 + N];
temp4 = area[N + N];
area[1] = W;
area[N] = W;
area[1 + N] = W;
area[N + N] = W;
solve();
dp[N][0] = min(dp[N][0] - 2, dp[N][0]);
res = min(res, dp[N][0]);
area[1] = temp1;
area[N] = temp2;
area[1 + N] = temp3;
area[N + N] = temp4;
}
}
printf("%d\n", res);
}
return 0;
}