같은 탑( BOJ 1126 )

문제 : https://www.acmicpc.net/problem/1126

1126번: 같은 탑

 

문제 파악하기

N개의 블럭이 있습니다. N개의 블럭을 적절하게 쌓아서 높이가 동일한 2개의 탑을 최대한 높게 만드는 것이 목표입니다. 

단순히 재귀함수 sv( idx, left, right) 를 만들기에는 left와 right에 최대 250,000까지 들어갈 수 있기에 메모리/시간 모두 부족합니다. 그렇다면 문제를 어떻게 추상화시킬 수 있을까요?

 

문제 해결하기

그렇다면 left와 right의 값 중 하나만 저장하는 것은 어떨까요? 예를 들어 left와 right 중 가장 큰 값만 저장하고, 나머지는 배열의 인덱스를 통해 유추할 수 있다면 우리는 3차원 배열이 아닌, 2차원 배열으로 문제를 해결할 수 있습니다. 그럼 이제 문제는 어떻게 2차원 배열을 정의할 것인지가 문제가 되겠네요.

 

사실 2차원 배열 중 첫번째 인덱스는 정해져 있습니다. 지금까지 우리가 확인한 블럭의 번호(idx)를 표시해야 합니다. 그럼 마지막 한 곳에는 어떤 값이 들어가는게 좋을까요? 단순히 생각하면 left값 하나를 저장하는걸 떠올릴 수 있습니다. 그리고 right값을 배열에 저장하면 우리는 3개의 값을 2차원 배열로 표현할 수 있습니다. 하지만 이렇게 될 경우에 점화식을 세울 수 없게 됩니다. left가 가질 수 있는 right의 값은 1개 이상이기 때문입니다.

 

예를 들어 (1, 3, 2, 4) 블럭이 있으며, sum[3][1]을 구한다고 가정해보겠습니다. sum[3][1]에 저장될 수 있는 값은 (3)과 (2) 그리고 (5), 총 3가지 입니다. 그럼 2가지 중 어떤 값을 저장해야 할까요? 단순히 1과 가장 가까운 값인 2를 선택하면 우리는 정답인 5를 구할 수 없습니다.

 

따라서, 우리는 다른 접근 방식이 필요합니다. 2번째 인덱스에는 left와 right의 차이(diff)를 표시해야 합니다. 그리고 배열에는 left와 right 중 큰 값을 저장하면 우리는 문제를 해결할 수 있는 점화식을 세울 수 있습니다.

 

sum[idx][diff] : idx번째 블럭을 사용하여 높이의 차이가 diff만큼 나는 2개의 탑을 만들었을 때, 가장 높은 탑의 높이

 

이렇게 배열을 정의한 후에는 현재 블럭(inp[idx])을 어디에 쌓는지에 따라 sum[idx][diff]의 값을 구할 수 있습니다. 여기서 중요한 점은 sum[idx][diff]에는 항상 최댓값이 저장해야 한다는 점입니다. 우리는 탑의 높이가 최대가 되길 원하며, diff의 값은 단순히 차이를 나타내고 있습니다. 따라서, 2개의 탑의 차이가 diff만큼 차이가 나는 경우 중 탑의 높이가 가장 큰 경우를 저장해야 우리가 원하는 결괏값을 얻을 수 있게 됩니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define NMAX 55
#define SMAX 500010
using namespace std;
 
int N;
int inp[NMAX], tot[NMAX];
 
int sum[NMAX][SMAX];
 
int abs(int k) { return k>0 ? k:-k; }
 
int main() {
    // input
    scanf("%d", &N);
    for(int i=1;i<=N;i++) {
        scanf("%d", &inp[i]);
 
        tot[i] = tot[i-1] + inp[i];
    }
 
    // sum[idx][diff]: idx까지 숫자를 사용했으며 차이값이 diff일 때, 나올 수 있는 가장 큰 값
    memset(sum, -1, sizeof(sum));
 
    for(int idx=0;idx<=N;idx++) {
        sum[idx][inp[idx]] = inp[idx];
 
        for(int diff=0;diff<=tot[idx] and idx>0;diff++) {
            // 현재 블럭을 사용하지 않았을 때
            if(sum[idx-1][diff] > 0) sum[idx][diff] = max( sum[idx][diff], sum[idx-1][diff] );
 
            // 현재 블럭을 높이가 낮은 탑에 쌓는 경우 1
            if(sum[idx-1][diff+inp[idx]] >= 0) sum[idx][diff] = max( sum[idx][diff], sum[idx-1][diff+inp[idx]] );
            if(sum[idx-1][abs(diff-inp[idx])] >= 0) {
                // 현재 블럭을 높이가 높은 탑에 쌓는 경우
                if(diff-inp[idx] > 0) sum[idx][diff] = max( sum[idx][diff], sum[idx-1][diff-inp[idx]] + inp[idx] );
 
                // 현재 블럭을 높이가 낮은 탑에 쌓는 경우 2
                else sum[idx][diff] = max( sum[idx][diff], sum[idx-1][inp[idx]-diff] + diff );
            }
        }
    }
 
    // print
    printf("%d", sum[N][0]);
 
}
 
/*
4
1 2 4 8
ans : -1
 
4
1 1 3 10
ans: 1
 
5
1 2 10 1 7
ans: 10
*/

 

 

후기

문제를 추상화하는 과정이 어려웠던 문제입니다. 배낭 문제처럼 구할 수 있는 모든 부분 집합의 합을 구하는 문제를 subsum problem이라고 한다는 것을 알게 되었으니 이참에 관련 문제를 공부하고 싶다는 생각이 듭니다. 테크닉이 필요하지 않은 동적 프로그래밍을 공부하는 사람들에게 추천하고 싶은 재미있는 문제입니다.

 

※ 추가 ※

2차원 배열을 1차원 배열 2개로 변환할 수 있습니다. 어짜피 이전 값(idx-1)만 사용하기 때문에 cur[diff]와 bef[diff]을 사용하여 문제를 해결할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define NMAX 55
#define SMAX 500010
using namespace std;
 
int N;
int inp[NMAX];
 
int cur[SMAX], bef[SMAX];
 
int abs(int k) { return k>0 ? k:-k; }
 
int main() {
    // input
    scanf("%d", &N);
    for(int i=1;i<=N;i++) scanf("%d", &inp[i]);
    
    memset(bef, -1, sizeof(bef));
    memset(cur, -1, sizeof(cur));
 
    bef[0] = 0;
    for(int idx=1;idx<=N;idx++) {
        cur[inp[idx]] = inp[idx];
 
        for(int diff=0;diff<=SMAX/2 and idx>0;diff++) {
            // 현재 블럭을 사용하지 않았을 때
            if(bef[diff] > 0) cur[diff] = max( cur[diff], bef[diff] );
 
            // 현재 블럭을 높이가 낮은 탑에 쌓는 경우 1
            if(diff+inp[idx]<=SMAX/2 and bef[diff+inp[idx]] >= 0) cur[diff] = max( cur[diff], bef[diff+inp[idx]] );
 
            if(bef[abs(diff-inp[idx])] >= 0) {
                // 현재 블럭을 높이가 높은 탑에 쌓는 경우 1
                if(diff-inp[idx] >= 0) cur[diff] = max( cur[diff], bef[diff-inp[idx]]+inp[idx] );
 
                // 현재 블럭을 높이가 낮은 탑에 쌓는 경우 2
                else cur[diff] = max( cur[diff], bef[inp[idx]-diff]+diff );
            }
        }
 
        // 현재 값을 이전 값으로 복사
        for(int i=0;i<=SMAX/2;i++) {
            bef[i] = cur[i];
            cur[i] = -1;
        }
 
    }
 
    // print
    printf("%d", bef[0]);
 
}
 
/*
4
1 2 4 8
ans : -1
 
4
1 1 3 10
ans: 1
 
5
1 2 10 1 7
ans: 10
*/