[BAE/<JOON> 문제풀이] 23085. 판치기

https://www.acmicpc.net/problem/23085

23085번: 판치기

서론

수학 문제나 그리디 문젠 줄 알았다. 근데 N 제한이 너무 작아서 그냥 브루트포스 했다.

---

풀이

원하는 위치의 동전을 골라서 뒤집을 수 있으므로 굳이 동전 배열 상태를 순서대로 저장할 필요가 없다.

앞면 동전 개수와 뒷면 동전 개수만 저장하면 된다.

반드시 정해진 k 개의 동전을 뒤집어야하므로 앞면 동전을 i개 뒤집었으면 반드시 뒷면 동전 k-i 개를 뒤집어야 한다.

총 k -1 개의 경우의 수가 나온다. 이걸 다 해보면 된다. 동전이 3000개 밖에 안되고 앞면 아니면 뒷면이니까 상태 저장 종류 수도 최대 3000개 밖에 안된다. 주의할 점은 앞면 동전이 i개 이상인지 뒷면 동전이 k - i개 이상인지를 검사하고 뒤집어야함.

---

코드

#include <bits/stdc++.h>
using namespace std;
using ll = unsigned long long;
struct bl {
    int p, h, cnt = 0;;
};
vector<bl> arr;
ll n, k, m;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k; cin >> n >> k;
    string s; cin >> s; int o = 0, e = 0; vector<int> dp(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        o += (s[i - 1] == 'H' ? 1 : 0);
        e += (s[i - 1] == 'T' ? 1 : 0);
    }
    if (o == 0) {
        cout << 0; return 0;
    }
    dp[o] = 1;
    queue<bl> q; q.push({ o, e, 0 });
    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        for (int i = 1; i <= k; i++) {
            if (cur.p >= i && cur.h >= k - i && dp[cur.p - i + (k - i)] == 0) {
                if (cur.p - i + (k - i) == 0) {
                    cout << cur.cnt + 1;
                    return 0;
                }
                dp[cur.p - i + (k - i)] = 1;
                q.push({ cur.p - i + (k - i), cur.h + i - (k - i), cur.cnt + 1 });                
            }
        }
    }
    cout << -1;
    return 0;
}