📝 문제 정보#
🧐 관찰 및 접근#
- 유명한 통곡의 벽 문제 초라기
- 문제가 $2 \times N$의 원형이라 조금 곤란하다.
- 쉬운 경우부터 생각하자.
- $1 \times N$의 선형이라면, 계단 수처럼 DP로 풀 수 있을 것 같다.
- $2 \times N$의 선형이라도 DP로 가능한 것 같다.
- 두칸 전에서 오는 것에 대해 가로두개 / 위에 가로와 아래 따로 / 아래 가로와 위에 따로
- 한칸 전에서 오는 것에 대해 세로 / 위아래 따로
- 이 5가지 경우에서 가능한 것 같다!
- 그런데 원형이라 조금 곤란한데..
- 뭔가 케이스를 나눌 수 있을 것 같긴 하다.
- 선형으로 생각했을때 맨 왼쪽에 대해, 그게 반대쪽과 이어진경우 / 안이어진경우.
- 위아래니까 각각 두가지, 총 4가지 경우의수를 따지면 될듯?
- 근데 이걸 어떻게 깔끔하게 코딩하지? 큰일났다.
- 둘다 반대쪽과 이어진 경우는 문제를 한칸 밀어서 풀기만 하면 되는 것 같은데, 한쪽만 밀린 경우가 까다롭다.
- 그런데 사실 모든 칸이 지그재그로 연결된 경우 빼고는 언젠가는 선형으로 풀어도 되는 타이밍이 있는 것 같다!
- 위에서 말한 타이밍은 예제에서는 $1-2, 10-11, 3-4, \cdots$로 연결된 느낌과 같다.
- 시간복잡도가 $O(NW)$이 되긴 하는데, 돌만하지 않을까? 저 지그재그만 예외처리를 해버리자.
- ㄲㅂ 시간초과네. 테케가 여러개라 그런 것 같다.
- 엥? 이거 그냥 길이를 $2N$으로 늘려서 하면 되지 않을까?
- …인줄알았는데 전이식 자체부터 두개 전에서 땡겨오다보니 차분트릭이 안먹히는것 같다.
- 전이식 자체에서도 여러칸 단위로 지그재그로 오면 할 수 있는게 없다..
- DP에서, 상태공간을 조금 더 정의해보자. $\text{DP}[i][j]$라고 하면, i번째칸까지 봤을때 위아래 찬게 j상황이라고 생각해보자. $j = 0, 1, 2, 3$에서 위아래 모두 빔, 위 참, 아래 참, 위아래 모두 참과 같은 느낌이다. 이렇게해서 전이식을 잘 세우면 저 예외상황들을 처리하기 용이할 것 같다.
- 3번은 0번과 같으니 없애고, 나머지 3개로 정말 잘 처리해보자…
💻 풀이#
- 코드 (C++):
void solve(){
ll N, W; cin >> N >> W;
vector<array<ll, 2>> v(N);
rep(i, 0, N) cin >> v[i][0];
rep(i, 0, N) cin >> v[i][1];
auto calc = [&](bool con1, bool con2) {
vector<array<ll, 3>> DP(N+1); // 0: 둘다끝, 1: 위가 튀어나감, 2: 아래가 튀어나감
rep(i, 0, N+1) rep(j, 0, 3) DP[i][j] = 1e18;
DP[0][0] = 0;
if(con1) DP[0][1] = 0;
if(con2) DP[0][2] = 0;
if(con1 && con2) DP[1][0] = 0;
rep(i, 1, N+1){
DP[i][0] = min(DP[i][0], DP[i-1][0] + (v[i-1][0] + v[i-1][1] <= W ? 1 : 2));
DP[i][0] = min(DP[i][0], DP[i-1][1] + 1);
DP[i][0] = min(DP[i][0], DP[i-1][2] + 1);
if(i-2 >= 0 && v[i-2][0]+v[i-1][0] <= W && v[i-2][1]+v[i-1][1] <= W){
DP[i][0] = min(DP[i][0], DP[i-2][0] + 2);
}
DP[i][1] = min(DP[i][1], DP[i][0] + 1);
if((i == N && con1) || (i < N && v[i-1][0] + v[i][0] <= W)){
DP[i][1] = min(DP[i][1], DP[i-1][0] + 2);
DP[i][1] = min(DP[i][1], DP[i-1][2] + 1);
}
DP[i][2] = min(DP[i][2], DP[i][0] + 1);
if((i == N && con2) || (i < N && v[i-1][1] + v[i][1] <= W)){
DP[i][2] = min(DP[i][2], DP[i-1][0] + 2);
DP[i][2] = min(DP[i][2], DP[i-1][1] + 1);
}
}
if(!con1 && !con2) return DP[N][0];
if(con1 && !con2) return DP[N-1][2] + 1;
if(!con1 && con2) return DP[N-1][1] + 1;
if(con1 && con2) return DP[N-1][0] + 2;
};
auto origin = v;
ll ans = 2*N;
rep(con1, 0, 2) rep(con2, 0, 2){
if(con1 && v[0][0] + v[N-1][0] > W) continue;
if(con2 && v[0][1] + v[N-1][1] > W) continue;
ans = min(ans, calc(con1, con2));
}
cout << ans << '\n';
}