BOJ 2499 의좋은 형제

의좋은 형제
(http://boj.kr/2499)

만약 \(i\)번째 열까지에서 합으로 \(k\)를 만들 수 있다면, \(i+1\)번째 열에서 \(k\)에 다음 열의 수를 더한 것도 만들 수 있다.
문제에서 합이 40000을 넘을 일이 없기 때문에, dp로 찾을 수 있다.
앞의 열의 높이가 현재보다 작아야거나 같아야한다는 점에 유의해서 잘 구현하면 된다.
형을 기준으로 했더니, n번째 행부터 시작해서 매우 헷갈린다.

마지막에 높이를 찾는 방법은, 가장 오른쪽 열부터 답이 되는 높이만큼의 합을 빼주면서 찾으면 된다.

#include <bits/stdc++.h>
 
using namespace std;
 
int mp[30][30], t[30][30], chk[30][40001];
 
int main() {
    int n, sum = 0, ans = 10000000;
 
    scanf("%d", &n);
 
    for (int i = 1;i <= n;++i)
        for (int j = 1;j <= n;++j) {
            scanf("%d", &mp[i][j]);
            sum += mp[i][j];
        }
 
    for (int i = 0;i <= n;++i) 
        chk[i][0] = 1;
 
    for (int i = -1;i < n;++i)
        for (int j = 1;j <= n;++j) {
            t[n - i][j] = t[n - i + 1][j] + mp[n - i][j];
            for (int k = 0;k + t[n - i][j] <= sum;++k)
                if (chk[j - 1][k] > 0) 
                    chk[j][k + t[n - i][j]] = i + 2;
        }
 
    for (int i = 0;i <= sum;++i)
        if (chk[n][i] > 0 && abs(sum - 2 * ans) > abs(sum - 2 * i))
            ans = i;
 
    printf("%d\n", abs(sum - 2 * ans));
    stack<int> anst;
    int now = ans;
    for (int i = n;i >= 1;--i) {
        anst.push(chk[i][now] - 1);
        now -= t[n - chk[i][now] + 2][i];
    }
    while (!anst.empty()) {
        printf("%d ", anst.top());
        anst.pop();
    }
 
    return 0;
}