[C++] 1126번 같은 탑 - DP

1. 문제

• N개의 정사각형 블록을 쌓아 두 개의 탑을 만드는데 이때 두 탑의 높이는 같다. 각 탑은 적어도 한 개의 블록을 포함해야 할 때 탑의 높이는 같다. 적어도 한 개의 블록을 포함해야 할 때 탑의 높이의 최댓값을 구하여라.

<입력>

• -1- 조각의 개수 \(N(1 \leq N \leq 50)\)
• -2- 각 조각의 높이가 주어짐 \(H(1 \leq H \leq 500,000)\)
• 모든 조각의 합은 500,000보다 작다

<출력>

• 문제의 정답을 출력하며, 불가능할 때는 -1을 출력한다.

2. 재정의

• 수열의 서로 겹치지 않는 두 부분 집합의 합이 같도록 하는 집합의 합의 최댓값을 구하시오

3. 해결방법

• max[i][k] = max(max[i-1][k+num[i]], max[i-1][abs(num[i]-k]))
• 차이가 k인 두 탑의 높이의 최댓값은 전 탑의 높이의 차가 k+num[i], abs(num[i]-k)인 것만 고려하면 된다.

4. 실수한 점, 개선할 점

• num[i]-k 뿐만 아니라 abs(num[i]-k)인 것도 고려해야 한다.
• 차이가 250,000일 때까지 고려할 필요가 없고 sum까지만 확인해주면 된다.
• 차이가 j인걸 고려할 때 [i-1][j]도 고려하여야 한다.
• i에 대한 결과를 모두 저장할 필요가 없기 때문에 [2][MAX_HEIGHT]크기의 배열만 정의해주면 된다.
• 차이가 j만큼 나는 것을 고려하지 않고 [i-1][j]에서 [i][j+num[i]]꺼를 바로 만드는 게 더 빠름. (이렇게 짠 코드가 보여서 아래에 링크를 달아놓음.)

 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>

using namespace std;

const int INF = 987654321;
const int MAX_N = 51;
const int MAX_HEIGHT = 500001;

//조각의 개수 N
int N;
//조각의 크기
int num[MAX_N];
//DP
int MaxRectangle[MAX_N][MAX_HEIGHT];
//차이의 max값
int sum;

int ret;

void input()
{
    cin >> N;
    for(int i=1; i<=N; i++)
        cin >> num[i];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    memset(MaxRectangle, -1, sizeof MaxRectangle);
    MaxRectangle[0][0]=0;
    
    for(int i=1; i<=N; i++) {
        sum+=num[i];
        for(int j=0; j<=(sum<=250000 ? sum:250000); j++) {
            //차이가 j인 두 탑의 최대 높이는 차이가 j+num[i]인 것과, 
            //num[i]-j인것 중 최댓값이다.
            int a, b;
            
            a = b = -1;
            a = MaxRectangle[i-1][j+num[i]];
            if(MaxRectangle[i-1][abs(j-num[i])]>=0)
                b = MaxRectangle[i-1][abs(j-num[i])] + min(j, num[i]);
            
            MaxRectangle[i][j] = max({a, b, MaxRectangle[i-1][j]});
        }
        ret = max(ret, MaxRectangle[i][0]);
    }
    cout << (ret ? ret:-1);
    
    return 0;
}

 

<참고한 코드(풀어야 볼 수 있습니다.)>

https://www.acmicpc.net/source/40442315

로그인

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.