BOJ 10649

10649번: 프리스비

농부 존과 그의 소들은 프리스비를 하며 놀고 있다. 베시가 프리스비를 던지자, 마크한테 갔고 결국 마크네 팀에게 프리스비가 넘어갔다! 마크의 키는 H이고(1 <= H <= 1,000,000,000), 마크 근처에 있

www.acmicpc.net

dp 풀이
비트마스킹 dp로 풀면 됨. S에 속하는 모든 i에 대해 i가 가장 밑에 가는 경우를 계산해주면 된다.
dp[S] = min(dp[S \ i], P[i] - sum(W[S \ i]))
S에서 높이 합이 H이상인 모든 경우에 대해 ans를 dp값으로 업데이트 해주면 된다.
그리디 풀이
S가 정해졌을때 P[i] + W[i]가 큰 순서대로 아래부터 쌓는 것이
min(P[i] - sum(W[1..(i - 1)])) = min(P[i] + W[i] - sum(W[1..i]))를 가장 크게 하는 것을
수학적 귀납법으로 증명할 수 있다.

dicohy27