백준 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;
}
여담
인간승리..!
탑다운으로 풀어보려고 했는데 잘 안돼서 바텀업으로 풀었다. 이게 문제별로 잘 풀리는 방식이 다르다고 한다. 앞으로는 억지부리지 말고 편해보이는 방식을 선택해야겠다. 유사코에서 올려준 풀이 참고.
레퍼런스
Author And Source
이 문제에 관하여(백준 10649번: 프리스비), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ks1ksi/백준-10649번-프리스비저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)