1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <iostream>    // 입출력 관련 라이브러리이다.
#include <vector>      // 동적 배열 사용을 위한 라이브러리이다.
#include <algorithm>   // max 함수 등을 사용하기 위한 라이브러리이다.
#include <cmath>       // abs 함수를 사용하기 위한 라이브러리이다.
using namespace std;

int main(){
    ios::sync_with_stdio(false);  // 입출력 속도 향상을 위한 설정이다.
    cin.tie(nullptr);             // cin과 cout의 동기화를 해제한다.
    
    int n;
    cin >> n;                     // 블록의 개수를 입력받는다.
    vector<int> blocks(n);
    int total = 0;                // 모든 블록의 높이 합을 저장할 변수이다.
    for (int i = 0; i < n; i++){
        cin >> blocks[i];         // 각 블록의 높이를 입력받는다.
        total += blocks[i];       // 블록의 높이를 total에 누적한다.
    }
    
    // dp[d]는 지금까지의 블록 배치로 두 탑의 높이 차이가 d일 때, 
    // 낮은 탑에 쌓인 블록들의 총 높이의 최댓값을 의미한다.
    // 도달할 수 없는 상태는 -1로 초기화한다.
    vector<int> dp(total + 1, -1);
    dp[0] = 0;                    // 초기 상태: 두 탑 모두 블록이 없는 상태이다.
    
    // 각 블록을 순회하며 dp 배열을 갱신한다.
    for (int h : blocks) {
        vector<int> ndp = dp;     // 현재 상태를 복사하여 새로운 상태 배열을 생성한다.
        for (int d = 0; d <= total; d++){
            if(dp[d] < 0) continue;  // 도달할 수 없는 상태는 건너뛴다.
            
            // 1. 블록을 사용하지 않는 경우: 상태 변화가 없으므로 그대로 유지된다.
            
            // 2. 블록을 높은 탑에 추가하는 경우:
            //    현재 높이 차 d에 h를 더하여 d+h가 되며, 낮은 탑의 높이는 그대로 유지된다.
            if(d + h <= total)
                ndp[d + h] = max(ndp[d + h], dp[d]);
            
            // 3. 블록을 낮은 탑에 추가하는 경우:
            //    두 탑의 높이 차는 abs(d-h)가 되며, 낮은 탑에는 min(d, h)만큼 높이가 추가된다.
            int nd = abs(d - h);
            ndp[nd] = max(ndp[nd], dp[d] + min(d, h));
        }
        dp = ndp;                 // 새로운 상태를 dp 배열에 반영한다.
    }
    
    // dp[0]이 양수이면 두 탑의 높이를 같게 만들 수 있는 경우이므로 결과를 출력하고,
    // 그렇지 않으면 -1을 출력한다.
    cout << (dp[0] > 0 ? dp[0] : -1) << "\n";
    return 0;                   // 프로그램을 정상 종료한다.
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import sys
input = sys.stdin.readline  # 빠른 입력을 위한 설정이다.

n = int(input())            # 블록의 개수를 입력받는다.
blocks = list(map(int, input().split()))  # 각 블록의 높이를 입력받아 리스트에 저장한다.
total = sum(blocks)         # 모든 블록의 높이 합을 계산한다.

# dp는 현재까지의 상태를 딕셔너리로 관리한다.
# 키(key)는 두 탑의 높이 차이를 나타내며, 값(value)은 낮은 탑에 쌓인 블록들의 총 높이의 최댓값이다.
dp = {0: 0}  # 초기 상태: 높이 차이가 0이며, 낮은 탑의 높이는 0이다.

# 각 블록을 순회하며 dp 상태를 갱신한다.
for h in blocks:
    new_dp = dp.copy()  # 기존 상태를 복사하여 새로운 상태 딕셔너리를 생성한다.
    for d, lower in dp.items():
        # 1. 블록을 사용하지 않는 경우: 상태 변화가 없으므로 그대로 유지된다.
        
        # 2. 블록을 높은 탑에 쌓는 경우:
        #    높이 차이가 d에서 d+h로 증가하며, 낮은 탑의 높이는 그대로 유지된다.
        new_d = d + h
        if new_d <= total:
            new_dp[new_d] = max(new_dp.get(new_d, -1), lower)
        
        # 3. 블록을 낮은 탑에 쌓는 경우:
        #    새로운 높이 차는 abs(d-h)가 되며, 낮은 탑에는 min(d, h)만큼 높이가 추가된다.
        new_d = abs(d - h)
        new_dp[new_d] = max(new_dp.get(new_d, -1), lower + min(d, h))
    dp = new_dp  # 갱신된 상태를 dp에 반영한다.

# 최종 상태에서 높이 차이가 0인 경우의 낮은 탑의 높이가 양수이면 결과를 출력하고, 그렇지 않으면 -1을 출력한다.
print(dp.get(0, -1) if dp.get(0, 0) > 0 else -1)