백준 25949번 Jar Game

문제 링크

$a,b,c$번 항아리에 남아있는 조약돌의 개수와 현재 턴으로 상태공간 정의.

$1\le a,b,c\le 100$이므로 턴이 별로 커지지 않는다.

적당히 30정도로 잡으면 모든 경우의 수에 대응할 수 있다. (${\sum }_{i=1}^{30}\ge a+b+c$)

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using ld = long double;
 
pair<int, int> cache[101][101][101][30];
 
pair<int, int> solve(int a, int b, int c, int turn) { // 홀수턴 F, 짝수턴 S
    if (!a && !b && !c) return {0, 0};
 
    pair<int, int>& ret = cache[a][b][c][turn];
    if (ret != make_pair(-1, -1)) return ret;
 
    vector<pair<int, int>> rets;
 
    if (a) {
        pair<int, int> tmp = solve(max(0, a-turn), b, c, turn+1);
        turn % 2 ? tmp.first += min(a, turn) : tmp.second += min(a, turn);
        rets.push_back(tmp);
    }
    if (b) {
        pair<int, int> tmp = solve(a, max(0, b-turn), c, turn+1);
        turn % 2 ? tmp.first += min(b, turn) : tmp.second += min(b, turn);
        rets.push_back(tmp);
    }
    if (c) {
        pair<int, int> tmp = solve(a, b, max(0, c-turn), turn+1);
        turn % 2 ? tmp.first += min(c, turn) : tmp.second += min(c, turn);
        rets.push_back(tmp);
    }
 
    pair<int, int> ans = {0, 0};
 
    for (auto& p : rets) {
        if (turn%2) {
            if (p.first > ans.first) ans = p;
        }
        else {
            if (p.second > ans.second) ans = p;
        }
    }
 
    return ret = ans;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int a, b, c;    
    cin >> a >> b >> c;
 
    fill(&cache[0][0][0][0], &cache[100][100][100][30], make_pair(-1, -1));
 
    auto [f, s] = solve(a, b, c, 1);
 
    // cout << "F: " << f << '\n';
    // cout << "S: " << s << '\n';
    
    if (f > s) cout << "F";
    else if (f < s) cout << "S";
    else cout << "D";
 
    return 0;
}

game dp에 대해 더 공부해봐야겠다.

2022 ICPC 예선문제인데 내년 ICPC 꼭 나가야지!