[BOJ] 백준 12886 - 돌 그룹

문제 링크

www.acmicpc.net/problem/12886

12886번: 돌 그룹

 

풀이

간단한 DP 문제입니다.

각 돌 그룹의 돌 개수를 상태로 하여 전개해줍시다.

 

주의할 점은 그룹당 가능한 돌의 개수가 1500개입니다. $O(1500^3)$으로 공간을 잡으면 메모리가 터지는데, 모든 돌의 개수는 항상 일정하다는 것을 생각하여 두 그룹의 돌 개수만 상태로 관리해도 괜찮습니다.

 

 

정답 코드

#include <bits/stdc++.h>
 
#define all(x) (x).begin(), (x).end()
using namespace std;
using vi = vector<int>;
 
bool chk[1555][1555];
 
int go(vi now) {
    int a = now[0], b = now[1], c = now[2];
    if (a == b && b == c) return 1;
    if (chk[b][c]) return 0;
    chk[b][c] = true;
    bool ret = false;
    auto getNext = [&](int x, int y, int z) {
        vi next = {x, y * 2, z - y};
        sort(all(next));
        return next;
    };
    if (b < c) ret |= go(getNext(a, b, c));
    if (a < c) ret |= go(getNext(b, a, c));
    if (a < b) ret |= go(getNext(c, a, b));
 
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int a, b, c;
    cin >> a >> b >> c;
    vi now = {a, b, c};
    sort(all(now));
    cout << go(now);
}