[알고리즘][10][백준_1126][C언어] - 같은 탑

 

 

---

문제이해

N개의 높이가 다른 블록들로 높이가 같은 두개의 탑을 쌓는데 그 탑의 높이가 최대일때의 그 높이를 구하는 문제이다.

 

단, 모든 블록을 사용할 필요가 없다.

 

 

---

알고리즘 설계

만약 블록을 쌓을때 구역 a와 b에 쌓아서 두개의 탑을 만든다고 할때 

 

각 블록마다

1. a에 쌓는다

2. b에 쌓는다

3. 둘다 쌓지않는다 ( 사용하지 않는다 )

 

3가지 경우가 있다.

 

여기서 한가지 정해놓고 갈 부분.

 

 

위 그림은 블록 4개로 탑을 쌓는과정중 일부인데 두 상황이 좌우에 누가 더 높냐만 다르지 25와 30으로 두 상황에서 두 탑의 높이가 동일하다. 따라서 함수를 진행하면서 a구역을 두 탑중 높은 탑, b구역을 두 탑중 낮은 탑으로 진행을 하게될것이고 해당 변수는 l ( large )과 s ( small )이다.

 

따라서 블록마다 가능한 경우를 다시 살펴보면

1. l 에 쌓는다 ( 높은곳에 쌓는다 )

2. s 에 쌓는다 ( 낮은곳에 쌓는다 )

3. 둘다 쌓지않는다 ( 사용하지 않는다 )

와 같다.

 

이렇게 하는 이유는 높이 구분 없이 좌,우로 쌓게되면 중복들이 많이 발생하고 비효율적이기 때문이다.

 

위의 경우대로 모두 해보면 n개의 블록에 대해 n^3 번의 결과를 살펴봐야하므로 더 효율적인 방안을 생각해볼 필요가 있다.

 

1. dp 이용

dp를 이용해 중복으로 방문하게 되는 경우를 체크해 시간을 줄여야한다.

 

 

위와 같이 만약 k번째 블록을 놓는 상황에서 왼쪽 상황을 이전에 방문했을경우 이후에 오른쪽 상황이 발생할 경우 이후에 최대로 쌓은수있는 같은 탑은 가보지 않아도 구할수 있다.

 

만약 좌측 상황에서 n까지 쌓았을때 최대 같은 탑의 높이가 100이였다고 해보자. 그렇다면 오른쪽 상황에서도 그 이전에 사용된 블록의 조합은 다르지만 최종적으로 k부터 n까지 블록을 사용해서 쌓을 수있는 최대 같은 탑 높이가 100인것은 동일할것이다.

 

 

 

그러나 이 규칙은 두 탑의 높이가 전부 같을 필요없이 두 탑의 차가 같아도 성립한다.

 

 

위의 상황을 보자. 둘다 동일하게 k번째 블록을 쌓아야하는 상황일때 좌측이 이미 방문했던 상황이고 우측이 아직 방문하지 않은 상황이다.

 

좌측에서 이미 높이가(50,40)일때 최대로 쌓을수 있는 높이가 100이라고 구했으므로 이는 결국 앞으로 큰쪽에+40, 작은쪽에+50 만큼 더 쌓을 수있다는 의미이므로 오른쪽 상황에서는 k번째부터 쌓아보지않아도 40+40, 30+50 = 80,80 으로 높이가 80인 두 탑을 쌓을 수 있다는 것을 알수있다.

 

따라서 dp배열에 저장할때 현재 블록 인덱스와 두 높이차를 이용해 앞으로 더 높은탑에 쌓을수 있는 최대 높이를 저장해두면된다.

 

dp[i][j] : i번째 인덱스를 쌓을때 현재 두 탑의 높이차가 j일때 높은탑에 쌓을수 있는 최대 블록들의 높이.

 

가 된다.

 

2. 조건 활용

문제에 주어진 조건을 활용해 불필요한 함수 진행을 줄이는 방법이 있다. 문제에서 각각의 블록들의 높이는 500000이하이고 모든 블록들의 높이의 합이 500000을 넘지 않는다고 했으므로 모든 블록들의 높이의 합의 최대는 500000미만이다.

 

따라서 최대로 두탑을 같게 쌓아도 250000을 넘길수 없다.

 

따라서 함수 진행중에 두탑중 높은쪽의 탑의 높이가 250000이 넘어가면 그 뒤로는 무조건 불가능함을 알수 있다. 따라서 입력된 블록들의 총 높이의 합이 h라면 그 때 최대 같은 탑 높이는 h/2 이하이다. 

 

또한 이를 활용하여 위의 dp배열에서 j의 범위를 알수 있는데 탑의 높이가 250000을 넘어갈수 없으므로 

dp[51][250001] 로 정의할수 있다.

 

이를 c언어로 구현하면 다음과 같다.

 

 

#include <stdio.h>
#include <stdlib.h>

int bl[51];
int dplarge[51][250001] = {0};
int n;
int max;
int maximum;

int block(int l, int s, int now);
int fmaximum(int x, int y);

int main(){
    int i;
    max = -2;
    maximum = 0;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&bl[i]);
        maximum = maximum + bl[i];
    }
    block(0,0,0);
    
    if(max == 0){
        printf("%d",-1);  
    }
    else{
        printf("%d",max);
    }
}

int block(int l, int s, int now){
    int tmp1,tmp2,tmp3,m;
    if(l == s){
        if(l > max){
            max = l;
        }
    }
    if(now == n || l > maximum/2){
        if(l == s){
            return l;
        }
        else{
            return -1;
        }
    }
    if(dplarge[now][l-s] != 0){
        if(dplarge[now][l-s] < 0){
            return -1;
        }
        else{
            if(l+dplarge[now][l-s] > max){
                max = l+dplarge[now][l-s];
            }
            return l+dplarge[now][l-s];
        }
    }
    tmp1 = block(l+bl[now],s,now+1);
    if(s+bl[now] > l){
        tmp2 = block(s+bl[now],l,now+1);
    }
    else{
        tmp2 = block(l,s+bl[now],now+1);
    }
    tmp3 = block(l,s,now+1);
    m = fmaximum(tmp1,fmaximum(tmp2,tmp3));
    dplarge[now][l-s] = m-l;
    return m;
}

int fmaximum(int x, int y){
    return (x > y) ? x : y;
}