C++로 해결하는 가장 높은 빌보드 문제

문제 설명

빌보드를 설치한다고 가정해 봅시다. 우리는 이 빌보드가 최대한 높은 높이를 갖기를 원합니다. 빌보드는 양쪽에 두 개의 강철 지지대로 받쳐지며, 두 지지대의 높이는 반드시 서로 같아야 합니다.

또한 서로 용접하여 연결할 수 있는 여러 개의 막대(rod)가 주어집니다. 예를 들어 길이가 1, 2, 3인 막대가 있다면, 이들을 모두 용접하여 길이 6짜리 하나의 지지대를 만들 수 있습니다.

목표는 빌보드를 지지할 수 있는 가장 큰 높이를 구하는 것이며, 빌보드를 지지하는 것이 불가능하다면 0을 반환해야 합니다.

예를 들어 입력이 [1,2,2,3,3,3,4]라면 출력은 9가 됩니다. [1,2,2,4]와 [3,3,3]이라는 두 부분 집합을 각각 좌우 지지대로 사용하면, 두 지지대의 총 길이가 모두 9로 같아지기 때문입니다.

해결 접근 방법

이 문제는 동적 계획법(DP)으로 해결할 수 있습니다. 핵심 아이디어는 두 지지대의 높이 차이를 DP 상태로 관리하는 것입니다. 차이 값은 음수가 될 수 있으므로, 오프셋 5000을 더해 인덱스 범위를 0부터 10000(N = 2 * 5000)으로 조정합니다. dp[i][j]는 i번째 막대까지 고려했을 때 두 지지대의 차이가 (j - 5000)일 때, 더 높은 쪽 지지대의 최대 높이를 의미합니다.

해결 단계는 다음과 같습니다.

sum := 0, n := 막대의 개수, N := 2 * 5000 으로 초기화합니다.
(n + 1) x (N + 1) 크기의 2차원 배열 dp를 정의하고 모든 값을 -1로 초기화합니다. (-1은 도달 불가능한 상태를 의미)
dp[0, 5000] := 0 으로 설정합니다. (두 지지대의 차이가 0이고 높이도 0인 초기 상태)
i를 0부터 n-1까지 반복합니다:
- j를 0부터 N까지 반복합니다:
  - x := rods[i]
  - 만약 j - x >= 0 이고 dp[i, j - x] != -1 이면:
    dp[i + 1, j] = max(dp[i + 1, j], dp[i, j - x] + x)
    (현재 막대를 더 높은 쪽 지지대에 추가하는 경우)
  - 만약 j + x <= N 이고 dp[i, j + x] != -1 이면:
    dp[i + 1, j] = max(dp[i + 1, j], dp[i, j + x])
    (현재 막대를 더 낮은 쪽 지지대에 추가하는 경우)
  - 만약 dp[i, j] != -1 이면:
    dp[i + 1, j] = max(dp[i, j], dp[i + 1, j])
    (현재 막대를 사용하지 않는 경우)
모든 반복이 끝나면 dp[n, 5000]을 반환합니다. 이는 두 지지대의 높이 차이가 0일 때의 최대 높이, 즉 정답입니다.

이 알고리즘의 시간 복잡도는 O(n * N), 공간 복잡도 역시 O(n * N)입니다.

아래 구현 예제를 통해 더 잘 이해해 보겠습니다.

예제 코드 (C++)

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int tallestBillboard(vector<int>& rods){
      int sum = 0;
      int n = rods.size();
      int N = 2 * 5000;
      vector<vector<int> > dp(n + 1, vector<int>(N + 1, -1));
      dp[0][5000] = 0;
      for (int i = 0; i < n; i++) {
         for (int j = 0; j <= N; j++) {
            int x = rods[i];
            if (j - x >= 0 && dp[i][j - x] != -1) {
               dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - x] +
               x);
            }
            if (j + x <= N && dp[i][j + x] != -1) {
               dp[i + 1][j] = max(dp[i + 1][j], dp[i][j + x]);
            }
            if (dp[i][j] != -1) {
               dp[i + 1][j] = max(dp[i][j], dp[i + 1][j]);
            }
         }
      }
      return dp[n][5000];
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,2,3,3,3,4};
   cout << (ob.tallestBillboard(v));
}

입력

{1,2,2,3,3,3,4}