[알고리즘 문제] 28220번 블록쌓기

 

출처 : https://www.acmicpc.net/problem/28220

28220번: 블록 쌓기

1. 문제 설명

1~N번 칸이 존재하며 i번 칸에 {A_i}개의 블록이 쌓여있다. 각 칸에 쌓인 블록의 개수가 L이상 R이하가 되면서 {A_i}를 오름차순이 되도록 배치하고자 한다. 블록은 한 번에 양 옆으로 한 개씩만 옮길 수 있다. 블록을 옮기는 횟수의 최솟값을 구하라.

 

2. 실패 1

1) 접근 과정

이 문제를 처음 봤을 때 해당 조건을 만족하되 {A_i}가 최소이면 될 것이라고 간과하였다. 그래서 그리디로 접근해 보았다. 

 

방법은 아래와 같다. i번째 칸에 대해 분석할 때 i-1까지는 이미 조건을 만족한다고 가정하고 "i+1~N번 칸의 평균값을 구하는 데, 해당 평균값이 i번째 칸의 값보다 커야한다." 를 만족하는 부등식을 통해 i번째 칸의 최소 값을 구할 수 있다. 따라서 해당 최솟값과 i-1번째 칸에 값 중 더 큰 것을 택하면 된다고 생각하였다. 

 

2) 오답 이유

당연하게도 i번째 칸이 최소여야 옮기는 횟수가 최소인 것이 아니다.

매우 간단한 반례로 1 9 같은 배치가 주어진다면 위의 방법은 뒤의 숫자를 고려하지 않았다는 뜻이다.

 

 

3. 실패 2

1) 접근 과정

실패 1을 통해 최솟값~최댓값 모든 경우에 대해 탐색하면 되지 않을까? 생각하였다. 이 과정에서 dp를 사용하면 O[N*[R-L]] 이기에 괜찮은 방법인 줄 알았다. 따라서 "dp[i][j] = i번째 칸이 j개의 블록이 쌓여있고 해당 조건을 만족할 때 최소 이동 횟수" 로 설정했다.

 

2) 오답 이유

위 처럼 dp테이블을 정의한다면 그 후의 블록 값들을 고려하지 않은 꼴이 된다. 해당 dp는 내가 원하는 정보를 충분히 담아내기는 힘들다. 따라서 이 아이디어도 틀리게 된다.

 

4. 성공

1) 접근 과정

그렇다면 내가 원하는 정보에 대해 정확히 정의할 필요가 있다. 

1. 작업하고 있는 칸의 번째 수, i

2. 여태까지의 최댓값 즉, i번째 칸에 배치할 블록의 수, j

3. 앞의 블록의 상태를 나타내는 수치, k

 

그리고 "빚" 이라는 개념을 정의했다. 이는 "앞에서 블록을 배치하기 위해 뒤에 있는 블록을 미리 가져다 썼다. 혹은 필요 없어서 앞으로 넘겼다." 를 표현하기 위해서 사용하였다. 그리고 이 수치를 [3]정보로 사용하고자 한다.

 

하지만 문제는 "빚"의 범위이다. 1번 빚이 최대 10억이기에 옳지 않다. 그렇다면 대신할 정보로 무엇이 있을까? 이는 바로 (입력값-L)의 누적합을 응용하는 것 이다. [2]번째 조건에서 배치할 블록의 수를 정했다면 [3]을 기존 k에서 j를 더한 값이 현재 상태가 된다. 그리고 처음 입력값을 이용한 누적합과 비교하면서 내가 여태 전에 몇 개를 주고 받았고 그로 인해 현재 칸에 블록이 몇 개 있는지 파악할 수 있는 것이다. 

 

2) 주의 사항

주의해야할 사항이 있다. i번째 칸에 j개를 배치할 때 참고할 값은 dt[i-1][1~j][~] 라는 사실이다. 따라서 이를 min값으로 갱신해야 하는데 문제는 3번째 칸이다. 2번째 칸에 맞춰서 3번째 칸을 쓰면 된다고 생각하였으나 내가 이 정보를 사용할 때 불러오는 값은 k이기 때문에 3번째 칸은 그냥 k로 전달받아야 한다. 이것을 생각하는 것이 생각보다 까다로웠는데 그 까닭은 dp를 모두 만족하지 않기 때문이다. 

 

참고로 해당 사실을 잘 생각해보면 윈도우 슬라이딩 알고리즘을 생각해볼 수 있다. 그리고 또 다른 점은 long long int 범위로 초기화를 21e8 로 설정하면 안된다는 점, 그리고 초기값의 누적합을 통해 불가능한 것은 미리 쳐내야 한다는 점이다. 

 

3) 코드

#include <bits/stdc++.h>
using namespace std;

#define ll long long int

int N, L, R;
ll dt[105][105][10005], num[105], sum[105];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> L >> R;
    for(int i=1; i<=N; i++){
        cin >> num[i];
        num[i] -= L;
        sum[i] = sum[i-1] + num[i];
    }
    for(int i=0; i<=N; i++){
        for(int j=0; j<=R-L; j++){
            for(int k=0; k<=10000; k++) dt[i][j][k] = 21e8 * 21e8;
        }
    }

    if(sum[N] < 0 || sum[N] > (R-L) * N){ cout << -1; return 0;}
    dt[0][0][0] = 0;
    for(int i=1; i<=N; i++){
        for(int j=0; j<=R-L; j++){
            for(int k=0; k<=sum[N]; k++){
                ll now = sum[i-1] - k + num[i], diff = now - j;
                if(j > 0)
                    dt[i-1][j][k] = min(dt[i-1][j][k],dt[i-1][j-1][k]);
                if(k + j > 10000) continue;
                if(i == N && k+j != sum[N]) continue;
                dt[i][j][k+j] = min(dt[i][j][k+j], dt[i-1][j][k] + abs(diff));
            }
        }
    }
    ll min_value = 21e8 * 21e8;
    for(int i=0; i<=R-L; i++)
        min_value = min(min_value, dt[N][i][sum[N]]);
    cout << min_value;
	return 0;
}

 

4. 소감

2일 동안 이것만 생각했는데... 생각보다 짜잘한 실수들이 많았던 것도 있지만 너무 단순하게 생각하고 코드를 짜버린 것이 컸던 것 같다. 그리고 3차원 dp는 많이 경험해 보지 않았기 때문에 관련 문제를 쫌 더 풀어봐야 겠다.. 그래도 엄청 어렵진 않고 알고나니 재밌었던 문제였다.