BOJ 2251번 물통

BOJ : https://www.acmicpc.net/problem/2251

github : https://github.com/junho0956/Algorithm/blob/master/2251/2251/%EC%86%8C%EC%8A%A4.cpp

 

문제에서 요구하는대로 구현하기는 했는데 썩 깔끔하지는 않다.

그 이유는 .. 아직 set 사용법에 대한 정확한 사용법을 몰라서

 

처음에는 typedef 로 선언해둔 구조체형인 pii 를 이용해서

set<pii> 형식으로 사용하였는데

다 코드한 후에 실행해보니, typedef 템플릿에 대한 어떤 컴파일 오류가 발생하였다.

오류를 이해하기 힘들어 이번에는 아래의 piiset 과 같은 선언을 이용해보았는데

다행히 컴파일오류가 나지 않아 AC 를 받게 되었다.

 

핵심은 문제가 요구하는 그대로 따라가주면 된다.

한 컵을 다 채우거나 자신의 컵이 비워질떄까지 채우기 위한 조건 그대로 코드해주면 된다.

 

맨 아래의 erase ( unique ~ ) 는 중복을 제거하는 방법으로,

 

간단히 설명하면

erase 가 컨테이너의 값을 지우는 함수이고

unique 는 컨테이너 내부의 값들 중 중복의 값이 없게 나열하는 함수이다.

unique 가 종료되고 나면 중복 정리가 끝난 뒷부분에 이터레이터가 반환되고,

이 부분부터 end 까지 erase 가 실행되어 중복제거가 완료된다.

 

set 을 쓰고나니 코드하는 부분이 더욱 편해진 것은 사실인 것 같다.

좀더 자주 사용해보도록 해야겠다.

 

#include <iostream>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
typedef struct pii {
    int a, b, c;
};
typedef pair<int, pair<int, int> > piiset;
 
vector<int> v;
queue<pii> q;
set<piiset> visit;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int A, B, C;
    cin >> A >> B >> C;
 
    q.push({ 0, 0, C });
 
    while (!q.empty()) {
        pii value = q.front();
        piiset valueset;
        valueset.first = value.a;
        valueset.second.first = value.b;
        valueset.second.second = value.c;
        q.pop();
 
        if (visit.find(valueset) != visit.end()) continue;
        visit.insert(valueset);
 
        if (value.a == 0) v.push_back(value.c);
        else {
            if (value.a <= B - value.b) q.push({ 0,value.b + value.a,value.c });
            else q.push({ value.a - (B - value.b), B, value.c });
            if (value.a <= C - value.c) q.push({ 0,value.b,value.c + value.a });
            else q.push({ value.a - (C - value.c), value.b, C });
        }
 
        if (value.b <= A - value.a) q.push({ value.a + value.b, 0, value.c });
        else q.push({ A, value.b - (A - value.a), value.c });
        if (value.b <= C - value.c) q.push({ value.a, 0, value.c + value.b });
        else q.push({ value.a, value.b - (C - value.c), C });
 
        if (value.c <= A - value.a) q.push({ value.a + value.c, value.b, 0 });
        else q.push({ A, value.b, value.c - (A-value.a) });
        if (value.c <= B - value.b) q.push({ value.a, value.b + value.c, 0 });
        else q.push({ value.a, B, value.c - (B - value.b) });
    }
 
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
 
    for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';
 
    return 0;
}