티스토리 뷰
728x90
문제 링크
풀이
간단한 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);
}
728x90
'알고리즘 > 문제 풀이' 카테고리의 다른 글
[BOJ] 백준 2281 - 데스노트 (1) | 2021.03.30 |
---|---|
[BOJ] 백준 2306 - 유전자 (0) | 2021.03.30 |
[BOJ] 백준 10800 - 컬러볼 (0) | 2021.03.30 |
[BOJ] 백준 1424 - 새 앨범 (0) | 2021.03.13 |
[BOJ] 백준 1670 - 정상 회담 2 (0) | 2021.03.13 |
댓글