백준 1126 - 같은 탑

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

 

다음 점화식을 정의한다.

 

dp(i, j) :=  i번째 블록에서 두 탑의 높이차가 j일 때 두 탑 중 높은 탑의 높이

 

그러면 다음과 같은 경우로 동적 계획법 계산을 할 수 있다.

 

1. i번째 블록을 쓰지 않는 경우

dp(i, j) = dp(i - 1, j)

 

2. i번째 블록을 높은 타워에 쌓는 경우

블록의 길이를 b라 하면 dp(i, j + b) = dp(i - 1, j) + b

 

3-1. i번째 블록을 낮은 타워에 쌓는데 그럼에도 불구하고 높은 타워보다 작은 경우

블록의 길이를 b라 하면 새로운 높이차 diff = j - b이다.

그러므로 dp(i, diff) = dp(i - 1, j)

 

3-2. i번째 블록을 낮은 타워에 쌓는데 높은 타워보다 커지는 경우

i - 1번째 블록까지 처리했을 때 낮은 탑의 높이 old = dp(i - 1, j) - j

블록의 길이를 b라 하면 i번째 블록을 쌓은 낮은 탑의 높이 new = old + b

i번째 블록을 쌓을 때 두 탑의 높이차 diff = new - dp(i - 1, j)

dp(i, diff) = new

 

바텀업 dp를 돌면서 위 4가지 경우를 계산하면 $O(NH)$의 시간 복잡도로 정답을 받을 수 있다.

 

전체 코드 - 첫 블록을 쓰지 않는 경우를 처리해야 함을 유의하고 높이차의 최대는 250000임을 기억하자.

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int n;
int ar[50];
int dp[51][250001];
 
void solve()
{
  memset(dp, -1, sizeof dp);
 
  cin >> n;
  for (int i = 0; i < n; i++) cin >> ar[i];  
 
  dp[0][ar[0]] = ar[0];
  dp[0][0] = 0;
 
  for (int i = 1; i < n; i++)
  {
    for (int j = 0; j <= 250000; j++)
    {
      if (dp[i - 1][j] == -1) continue;
 
      dp[i][j] = max(dp[i][j], dp[i - 1][j]);
 
      int high_tower = dp[i - 1][j] + ar[i];
      if (high_tower <= 250000)
      {
        dp[i][j + ar[i]] = max(dp[i][j + ar[i]], high_tower);
      }
 
      int low_tower;
      int diff = ar[i] - j;
 
      if (diff > 0 and diff <= 250000)
      {
        low_tower = dp[i - 1][j] + diff;
        dp[i][diff] = max(dp[i][diff], low_tower);
      }
      else if (abs(diff) <= 250000)
      {
        dp[i][-diff] = max(dp[i][-diff], dp[i - 1][j]);
      }
    }
  }
 
  cout << (dp[n - 1][0] == 0 ? -1 : dp[n - 1][0]);
}
 
int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록