프리스비

백준 10649번: 프리스비

아이디어

현재 선택된 소 집합을 비트로 표현한다. 해당 소 집합에 대해 가장 큰 안정도를 기록한다.
가장 큰 안정도를 구하는 방법은 다음과 같다.

i는 현재 가장 큰 안정도를 구하려는 소 집합, j는 그 소 집합에 속한 소 한마리.
i에 포함된 모든 j에 대해

st[i] = max(st[i], max(min(st[i-(1<<j)]-arr[j].weight, arr[j].power), min(arr[j].power-cw[i-(1<<j)], st[i-(1<<j)])));

점화식이 너무 길어서 어지럽다. 소 집합에 포함된 소를 한마리 선택하고, 그 소를 맨 위로 올리는 경우, 맨 아래로 내리는 경우 두 가지중에 안정도가 더 큰 경우를 선택한다. 이를 소 집합에 포함된 모든 소에 대해 반복한다.
소를 맨 위로 올리는 경우는 전체 안정도에서 자기 무게를 뺀 값과 자기 자신의 힘 두 값중 더 작은 값이다.
소를 맨 아래로 내리는 경우는 자기 자신의 힘에서 전체 무게를 뺀 값과 전체 안정도 두 값중 더 작은 값이다.

코드

#include <bits/stdc++.h>

using namespace std;

typedef struct _cow {
    long long height, weight, power;
} Cow;

int N, H;
Cow arr[20];

long long ch[1<<20];
long long cw[1<<20];
long long st[1<<20];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> H;

    for (int i = 0; i < N; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        arr[i] = {a, b, c};
    }
    
    memset(st, -1, sizeof(st));
    st[0] = LLONG_MAX;
    
    for (int i = 1; i < (1<<N); i++) {
        for (int j = 0 ; j < N; j++) {
            if (i&(1<<j)) {
                ch[i] = ch[i-(1<<j)]+arr[j].height;
                cw[i] = cw[i-(1<<j)]+arr[j].weight;
                st[i] = max(st[i], max(min(st[i-(1<<j)]-arr[j].weight, arr[j].power), min(arr[j].power-cw[i-(1<<j)], st[i-(1<<j)])));
            }
        }
    }
    
    long long ans = -1;
    for (int i = 0; i < (1<<N); i++) {
        if (ch[i] >= H) {
            ans = max(ans, st[i]);
        }
    }
    if (ans == -1) cout << "Mark is too tall";
    else cout << ans;
    return 0;
}

여담

인간승리..!
탑다운으로 풀어보려고 했는데 잘 안돼서 바텀업으로 풀었다. 이게 문제별로 잘 풀리는 방식이 다르다고 한다. 앞으로는 억지부리지 말고 편해보이는 방식을 선택해야겠다. 유사코에서 올려준 풀이 참고.

레퍼런스

USACO Solution