BOJ 26969 Bribing Friends

📝 문제 정보

#

• 링크: https://www.acmicpc.net/problem/26969
• 번역

문제 번역

#

Bessie는 “소 유전체학: 다큐멘터리"를 보고 싶지만, 혼자 가고 싶지 않습니다. 불행히도, 그녀의 친구들은 함께 갈 만큼 열정적이지 않습니다! 따라서 Bessie는 친구들이 영화관에 함께 가도록 뇌물을 줘야 합니다. 그녀는 두 가지 뇌물 수단을 가지고 있습니다: 무니(mooney)와 아이스크림 콘입니다.

Bessie는 $N$명 ($1 \le N \le 2000$)의 친구가 있습니다. 하지만 모든 친구가 똑같지는 않습니다! 친구 $i$는 인기도 점수 $P_i$ ($1 \le P_i \le 2000$)를 가지고 있으며, Bessie는 자신과 함께 가는 친구들의 인기도 점수 합을 최대화하고 싶습니다. 친구 $i$는 Bessie가 $C_i$ ($1 \le C_i \le 2000$) 무니를 주면 함께 가려고 합니다. 또한 Bessie가 $X_i$ ($1 \le X_i \le 2000$)개의 아이스크림 콘을 주면 1 무니의 할인을 제공합니다. Bessie는 할인으로 인해 친구가 그녀에게 무니를 주지 않는 한, 한 친구로부터 원하는 만큼 정수 단위의 할인을 받을 수 있습니다.

Bessie는 $A$개의 무니와 $B$개의 아이스크림 콘을 가지고 있습니다 ($0 \le A, B \le 2000$). 그녀가 무니와 아이스크림 콘을 최적으로 사용했을 때 달성할 수 있는 인기도 점수 합의 최댓값을 구하는 것을 도와주세요!

입력

#

첫 번째 줄에는 세 개의 숫자 $N$, $A$, $B$가 주어지며, 각각 친구의 수, Bessie가 가진 무니의 양, 아이스크림 콘의 개수를 나타냅니다.

다음 $N$개의 줄 각각에는 세 개의 숫자 $P_i$, $C_i$, $X_i$가 주어지며, 각각 인기도 ($P_i$), 친구 $i$가 Bessie와 함께 가도록 하는 데 필요한 무니 ($C_i$), 친구 $i$로부터 1 무니 할인을 받는 데 필요한 아이스크림 콘 ($X_i$)을 나타냅니다.

출력

#

Bessie가 무니와 아이스크림 콘을 최적으로 사용했을 때, 함께 가는 친구들의 인기도 점수 합의 최댓값을 출력합니다.

🧐 관찰 및 접근

#

• 2초에 $O(NAB)$ 8억을 믿어볼까?
  • 아 나이브는 아이스크림 콘을 몇개 줄지를 몰라서 심지어 세제곱도 넘는다 ㅋㅋ
• 이번에도 BOJ 13448 SW 역량 테스트 문제처럼 좀 그리디하게 생각해보자.
• 살 소들을 정했다면, $X$가 작은 소들을 먼저 꼬셔서 무니를 할인받는게 이득이다.
  • 잉 이것만해도 세제곱이 보장되는것같다
  • 근데 세제곱이 안돈다 ㅋㅋ
• 고민해보니, 앞에서는 콘을 열심히 퍼주다가 / 한 친구한테는 섞어서 주다가 / 그뒤부터는 그냥 무니로 사야하는 것 같다
  • 세제곱에서 제곱으로 줄일 수 있겠다!

💻 풀이

#

• 코드 (C++):

void solve(){
    cin >> N >> A >> B;
    vector<Friend> Frd(N);
    rep(i, 0, N) cin >> Frd[i].P >> Frd[i].C >> Frd[i].X;
    sort(all(Frd), [](Friend &A, Friend &B){
        return A.X < B.X;
    });

    rep(i, 0, N){
        auto [P, C, X] = Frd[i];
        rrep(j, 0, B+1){
            DPprf[i+1][j] = max(DPprf[i+1][j], DPprf[i][j]);
            if(j - X*C < 0) continue;
            DPprf[i+1][j] = max(DPprf[i+1][j], DPprf[i][j - X*C] + P);
        }
    }

    rrep(i, 0, N){
        auto [P, C, X] = Frd[i];
        rrep(j, 0, A+1){
            DPsuf[i][j] = max(DPsuf[i][j], DPsuf[i+1][j]);
            if(j - C < 0) continue;
            DPsuf[i][j] = max(DPsuf[i][j], DPsuf[i+1][j-C] + P);
        }
    }

    int ans = max(DPprf[N][B], DPsuf[0][A]);
    rep(i, 0, N){
        auto [P, C, X] = Frd[i];
        rep(j, 0, B+1){
            int mxDiscount = min(C, j / X);
            int moonie = A - (C - mxDiscount), cones = B - j;
            if(moonie < 0 || cones < 0) continue;
            ans = max(ans, P + DPprf[i][cones] + DPsuf[i+1][moonie]);
        }
    }
    cout << ans;
}