BOJ 1128 피보나치 냅색

BOJ 1128 피보나치 냅색

[분류 - 브루트포스, 수학]

 

  어렵다ㅏㅏ

 

[풀이]

  [표현식] 제켄도르프의 정리(https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem)에 의하면 1보다 크거나 같은 자연수는 모든 계수는 0또는 1이고 인접한 피보나치 수에 대한 계수 ei × ei-1 = 0인 피보나치 수열로 표기할 수 있다. 또 이 수열은 유일(unique)하다. 

  [전파] 가변량 ei를 i번째 피보나치 수에 대응되는 물건을 몇 개 쓸 수 있는지를 나타낸다고 정의하자.

  주어진 무게 C에 대해 ei = 1인 가장 큰 피보나치 수 Fi에 대해 생각해보자. Fi 무게를 가지는 물건을 가방에 넣지 않으면 이 계수 ei는 이전 피보나치 Fi-1, Fi-2에 전파된다. 따라서 ei-1과 ei-2가 증가함을 알 수 있다. 전파하는 과정에서 이 계수들 역시 피보나치 수열만큼 증가한다.

 

  또 하나 관찰할 점은 방금 과정(물건을 넣지 않고 전파를 하는 과정)을 계속 진행한다고 했을 때 i-3번째 즉 ei-3부터 e1까지는 전혀 영향을 받지 않는다는 것이다. 맨 앞에 있는 i-1번째와 i-2번째만 바뀌므로 나머지 반열린구간 [1, i-2)는 제켄도르프의 표현식을 유지하게 된다.

 

  [이래서 다이나믹인가 ?] 그럼 dp구성을 3차원으로 하면 될까?

$$dp[i][i_0][i_1] = i번째 피보나치 수 F_i에 대해 e_i가 i_0이고 e_{i-1}가 i_1 일 때 최대가치$$

  [반례 - 더 담을 수 있을텐데..] 하지만 그렇게 호락호락하지 않다..
  예를 들어 C=10, w1=8, v1=1 w2=w3=5, v2=v3=4, w4=2, v4=1이라 하자. (wi = i번째 물건의 무게, vi= i번째 물건의 가치)

  C를 제켄도르프 표현식으로 나타내면 계수열 e = 10010 로 구할 수 있다. 8(=F5, 첫 번째 물건)을 사용하지 않으면 01110과 동치가 되는데, e4와 e3이 모두 1로 처리되기 때문에 5를 한 번밖에 사용하지 못한다고 계산해버린다. 실제는 e3, e2를 합쳐서 e4에 한 번 더 추가할 수 있기에 총 두 번 사용할 수 있다. 물론 dp를 4차원으로 구성한다고 해도 문제가 해결되진 않는다.

 

  [다이나믹 실패] 따라서 이런 연쇄를 생각하면 앞의 두 수뿐만 아니라 모든 계수를 상태(state)로 둬야하기 때문에 불가능한 접근법이다.

---

  [브루트포스] 모든 경우의 수를 생각해보자. 물건마다 넣을 것인지 안넣을 것인지 판단하기 때문에 경우의 수는 2^N개가 나온다. 상태 이전에서 이진 트리가 나오게 되는데, 왼쪽 자식을 현재 물건을 선택 안했을 때, 그리고 오른쪽 자식을 현재 물건을 선택 했을 때의 상태로 보자.

  [가지치기 - 왼쪽 자식] 전파에 대해 다시 떠올려보자. 현재 물건을 사용하지 않는다면(엄격하게 Fi에 해당하는 무게를 가지는 어느 물건도 사용하지 않는다면), 전파가 일어나는데 이 역시 피보나치 수를 나타냄을 위에서 확인했다. 그런데 물건이 총 50개밖에 되지 않으므로 왼쪽 자식으로만 타고 내려간다면 그 깊이는 얼마나 될까. ei=1이라면 ej(j < i)가 50 이상인 구간까지만 가면 된다. 이유는 물건의 개수는 50개 밖에 되지 않기 때문에 어느 j번째 노드에서 계수가 50이상이 되버리면 모든 물건을 담을 수 있다는 것과 동치이기 때문이다. 50 이상이 되는 깊이는 10이므로 왼쪽으로 가는 노드는 최대 깊이 10밖에 되지 않는다.

  [가지치기 - 오른쪽 자식] 똑같은 무게를 가지는 아이템 Fi=Fj(i != j)에 대해 vi < vj인 경우를 생각해보자. j번째 물건을 담지 않았는데 i번째 물건을 담을 필요는 없다. 즉, 같은 무게에 다른 가치에 대해 더 높은 가치의 물건을 사용하지 않았는데, 낮은 가치의 물건을 사용할 필요는 없다.

 

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 50;
using ll = long long;
ll psw[MAX_N], psc[MAX_N];
int N;
vector<pair<ll, ll>> items;
ll rec(int p, ll C, bool usedBig) {
    if (p < 0) return 0;
    if (psw[p] <= C) return psc[p];
    else if (items[p].first <= C && (usedBig || items[p + 1].first != items[p].first))
        return max(rec(p - 1, C - items[p].first, 1) + items[p].second, rec(p - 1, C, 0));
    else return rec(p - 1, C, 0);
}
int main() {
    int T, i;
    ll C;
    scanf("%d", &N);
    items.resize(N);
    for (i = 0; i < N; i++)
        scanf("%lld%lld", &items[i].first, &items[i].second);
    sort(items.begin(), items.end());
    psw[0] = items[0].first, psc[0] = items[0].second;
    for (i = 1; i < N; i++)
        psw[i] = psw[i - 1] + items[i].first, psc[i] = psc[i - 1] + items[i].second;
    scanf("%lld", &C);
    printf("%lld\n", rec(N - 1, C, 1));
    return 0;
}