EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2) D. World is Mine

 

 

문제 링크

• Problem - D - Codeforces

Problem - D - Codeforces

 

 

문제 풀이

 

평소에 그냥 딱 하고 풀리던 Dp문제들과 다르게 조금 오래걸려서 풀이를 쓰면서 익숙해지려고 한다. 왜 풀리는지 살짝 이해가 안 돼서 써보면서 나도 이해하려고 한다.

 

일단 Alice 는 케이크를 무조건 가중치가 적은 것부터 먹는 게 유효한 전략이다.

따라서, 배열의 값들을 잘 압축하고, 갯수를 세서 재정렬한다. 즉, {4, 6, 1, 3} 이와 같이, 가중치가 낮은 순으로 정렬해서, 개수만 나는 담았다.

 

그럼 Bob이 Alice를 방해하는 전략이 중요하다. 근데, 전략이 유효한 전략이 없어서, 다이나믹 프로그래밍으로 모든 경우의 수를 적절하게 시행해야 한다.

 

이 시행방법을 잘못 찾고 있었는데, dp테이블에 아무것이나 정의하다 보니까, 딱 들어맞는 걸 발견하게 되었다.

 

$dp[i][j]$ 를 i번째 케이크까지 Alice 가 먹든 안 먹든 했을 때, bob이 j번 케이크를 먹을 수 있을 때의 Alice가 먹은 케이크 개수 중 최솟값이다.

 

i번째 가중치를 가진 케이크까지 왔을 때, bob이 먹어야 할지, 안먹어야 할 지 결정해야 한다. 근데 이때, i번째 가중치를 가진 케이크를 Alice가 먹지 못하게 하려면, bob이 그 케이크의 개수를 다 먹어야 하기 때문에, 값 j도 필요하게 되었다.

 

$$dp[i][j] = \min(dp[i-1][j-1] + 1, dp[i-1][j+W[i]])$$

$$dp[1][1] = 1$$

$dp[1][1] = 1$ 인 이유는, 첫 번째 케이크는 Alice가 무조건 먹고 시작하기 때문이다.

#include<bits/stdc++.h>

typedef long long lint;
using namespace std;

int nums[5050], dp[5050][5050];

typedef pair<int, int> pt;
vector<int> vc;

void solve () {
    int N; cin >> N;

    fill(nums, nums+5050, 0);
    vc.clear();

    for (int i=0;i<N+30;i++) {
        for (int j=0;j<N+30;j++) {
            dp[i][j] = 1e9;
        }
    }

    dp[1][1] = 1;

    for (int i=0;i<N;i++) {
        int c; cin >> c;
        vc.push_back(c);
        nums[c]++;
    }

    sort(vc.begin(), vc.end());
    vc.erase(unique(vc.begin(), vc.end()), vc.end());

    for (int i=1;i<vc.size();i++) {
        for (int j=0;j<=N;j++) {
            dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + 1);
            if (j-nums[vc[i]] >= 0) {
                int &x = dp[i+1][j-nums[vc[i]]];
                x = min(x, dp[i][j]);
            }
        }
    }

    int ans = 1e9;
    for (int i=0;i<=N;i++) ans = min(ans, dp[vc.size()][i]);
    cout << ans << '\n';
}

int main () {
    cin.tie(0);ios_base::sync_with_stdio(0);
    int _; cin >> _;
    while(_-->0) solve();
}