PS 일기 2024년 2월 8일 (3일 차) (28220번 블록 쌓기)

PS 일기 2024년 2월 8일 (3일 차)

PS 일기란?

PS 실력 향상을 목적으로 날마다 푼 문제를 회고하는 것입니다. 문제의 간단한 해법과 함께 어떤 방식으로 접근했는지, 그리고 문제의 해법을 찾는 데 결정적이었던 깨달음은 무엇이었는지 등을 기록합니다.

오늘의 문제

28220번 블록 쌓기

알고리즘 분류

• DP
• 누적합

문제 설명

블록을 쌓을 수 있는 $N$개의 칸이 있고 각 칸에는 $A_i$개의 블록이 쌓여 있습니다. 각 칸의 각 블록은 인접한 칸으로 옮길 수 있습니다. 아래의 조건을 만족하기 위해 블록을 옮기는 최소 횟수를 구해야합니다.

• 각 칸에 쌓인 블록의 개수가 $L$개 이상 $R$개 이하입니다.
• 각 칸의 쌓은 블록의 개수는 단조증가합니다.

문제 풀이

관측 1

빌림의 정도를 정수로 표현 할 수 있습니다.

$i$번째 칸에 블록을 추가하기 위해 $j(1 \leq j < i)$에서도 $j(i < j \leq N)$에서도 블록을 가져올 수 있습니다. 다르게 말하면 너무 자유롭습니다. 그래서 빌림을 정의해 이를 표현할 것입니다. $i$번째 칸의 높이를 $h$로 한다고 했을 때 빌름을 $A_i - h$로 정의 할 수 있습니다. 만약 빌림이 음수라면 빌려오는 것이고 양수라면 빌려주는 것입니다.

아래와 같은 입력이 주어질때 빌림은 다음과 같습니다.

5 3 5
2 0 9 1 4

$h \backslash\ i$	1	2	3	4	5
3	-1	-3	6	-2	1
4	-2	-4	5	-3	0
5	-3	-5	4	-4	-1

각 열에 하나의 행을 택하여 그를 모두 더한 값이 0이라면 성공적으로 완료된 것입니다.

관측 2

점화식은 $D_{i, j, k} = \min_{l = L}^{j} D_{i-1, l, k + A_i - l} + abs(k)$ 입니다.

$D_{i, j, k}$를 i번째까지 계산했을때 $i$번칸의 블럭개수가 $j$이고 $k$개의 블록이 부동일때 최소 움직임이라고 정의

관측 3

상한과 하한을 정할 수 있습니다.

$D_{i, j, k}$를 계산할때 $k$는 $\sum_{l=i+1}^{N} L-A_l \leq k \leq \sum_{l=i+1}^{N} R-A_l$ 입니다. $k$는 $i$번째 칸 이후에 얻을 수 있는 최저 빌림의 합과 최대 빌림의 합의 사이여야하기 때문입니다.

관측 4

점화식을 개선할 수 있습니다.

점화식의 정의를 살짝 바꾸면 더 $O(N^3 (R-L))$에 구할 수 있습니다. $D_{i, j, j}$를 $i$번째까지 계산했을때 $i$번칸의 블럭개수가 $j$이하이고 $k$개의 블록이 부동일때 최소 움직임이라고 정의하면 $D_{i, j, k} = \min(D_{i-1, j, k + A_i - j} + \vert k \vert, D_{i, j - 1, k})$입니다.

구현

의존성을 지키기 위해서 점화식의 순서를 조금 바꿨습니다. 또 슬라이딩 윈도우 등의 방법을 이용하면 더 나은 구현을 할 수 있겠지만 저의 머리가 따라가지 못해 단순하게 구현하였습니다. 제 코드를 보는것 보단 KOI 모범코드를 보는 것을 추천합니다. 이 코드는 제가 봐도 못알아 먹겠네요.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int MAXN = 105;
const ll INF = 1e18;

ll N, L, R, arr[MAXN], mn[MAXN], mx[MAXN], dp[MAXN][105][10005];

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> N >> L >> R;
    for(ll i = 1; i <= N; ++i) {
        cin >> arr[i];
    }
    for(ll i = N; i >= 1; --i) {
        mn[i] = L - arr[i] + mn[i+1];
        mx[i] = R - arr[i] + mx[i+1];
        assert(0 <= mx[i] - mn[i] && mx[i] - mn[i] <= 10000);
    }

    fill((ll*)dp, (ll*)dp + sizeof(dp) / sizeof(ll), INF);
    if(0 < mn[1] || mx[1] < 0) goto NOT_FOUND;

    for(ll i = L; i <= R; ++i) {
        ll v = arr[1] - i;
        if(v < mn[2] || mx[2] < v) continue;
        dp[i-L+1][1][v-mn[2]] = abs(v);
    }

    for(ll i = L; i <= R; ++i) {
        for(ll j = 1; j <= N; ++j) {
            if(i == L && j == 1) continue;
            for(ll k = mn[j+1]; k <= mx[j+1]; ++k) {
                ll& cur = dp[i-L+1][j][k-mn[j+1]];

                ll cand = dp[i-L][j][k-mn[j+1]];
                cur = min(cand, cur);

                ll prv = k - (arr[j] - i);
                if(prv < mn[j] || mx[j] < prv) continue;

                cand = dp[i-L+1][j-1][prv-mn[j]] + abs(k);
                cur = min(cand, cur);
            }
        }
    }

    if(dp[R-L+1][N][0] >= INF) goto NOT_FOUND;
    cout << dp[R-L+1][N][0] << "\n";
    return 0;
NOT_FOUND:
    cout << "-1\n";
    return 0;
}