BOJ 3363 : 동전

• 문제 링크 : boj.kr/3363
• 난이도 : G5
• 태그 : 브루트포스, 구현

3363번: 동전

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

struct measurement {
    int a[4];
    int c;
    int b[4];
};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    vector<int> arr(12, 10);

    measurement input[3];
    for(int i = 0; i < 3; i++) {
        cin >> input[i].a[0] >> input[i].a[1] >> input[i].a[2] >> input[i].a[3];
        string s;
        cin >> s;
        if(s == "<") input[i].c = -1;
        if(s == "=") input[i].c = 0;
        if(s == ">") input[i].c = 1;
        cin >> input[i].b[0] >> input[i].b[1] >> input[i].b[2] >> input[i].b[3];
    }
    
    vector<int> cand;
    for(int i = 0; i < 24; i++) {
        arr[i/2] += (i%2 ? 1 : -1);
        bool res = true;
        for(int j = 0; j < 3; j++) {
            int sa = 0, sb = 0;
            for(auto u : input[j].a) sa += arr[u-1];
            for(auto u : input[j].b) sb += arr[u-1];
            if(input[j].c == -1) {
                if(sa < sb) res &= true;
                else res &= false;
            }
            if(input[j].c == 0) {
                if(sa == sb) res &= true;
                else res &= false;
            }
            if(input[j].c == 1) {
                if(sa > sb) res &= true;
                else res &= false;
            }
        }
        if(res) cand.push_back(i);
        arr[i/2] = 10;
    }

    if(cand.size() == 1) {
        cout << cand[0] / 2 + 1;
        cout << (cand[0]%2 ? "+" : "-");
    }
    if(cand.size() == 0) cout << "impossible";
    if(cand.size() > 1) cout << "indefinite";

    return 0;
}

---

풀이

언뜻 보기엔 문제가 복잡해보인다. 하지만 나올 수 있는 경우를 생각해보면 각각의 동전이 무겁거나 가벼운 경우로 총 24가지밖에 없다. 따라서 브루트포스로 해결할 수 있다.

구현은 입력, 후보 판별, 정답 세 부분으로 나누어 구현한다.