UCPC 2024 예선 후기 및 풀이

July 17, 2024

Updated: August 1, 2024

Tags: Union-Find, 구현, 그리디, 많은-조건-분기, 문제-풀이-후기, 스택, 완전-탐색, 해구성하기

2024 UCPC 예선을 참가했다.
사실 팀으로서 처음 참가하는 거라 기대했고 즐거운 경험이었다.
하지만 연습 때는 꽤 솔브를 많이 받았는데, 실전에서는 2솔 밖에 받지 못 했다.

원인은 실력부족, 경험부족이었다.
연습 때도 시간을 잡고 했지만 실전의 스코어보드가 주는 압박감과 내가 무언가를 해내야 한다는 심리적 쫓김으로 인해 온전히 집중하지 못 했고, 무엇보다도 이런 컨디션에 쉽게 흔들려버리는 실력의 부재가 가장 큰 원인이라 생각된다.
그래도 이렇게 한 번 망해보는 경험이 큰 도움이 될 것이라는 건 팀원들 모두의 공통의 의견이었다. (~~한 번 망해볼 때가 된 것이라는.. ㅎ~~)

내가 어떤 부분이 부족했는지나 공부를 하기 위해 업솔빙을 해 보겠다.
전부 풀지는 않았고 풀 수 있으면서 난이도가 적절한 문제들만 몇 개 골라서 풀었다.

C. 미어캣

한 기준점을 잡아놓고,
그 기준점을 중심으로 왼쪽은 왼쪽을 바라보는 미어캣들이 최대한 많이 볼 수 있게 하고,
기준점의 오른쪽은 오른쪽을 바라보는 미어캣들이 최대한 많이 볼 수 있게 하면 된다.

시작하기 전, 같은 방향을 바라보는 미어캣들끼리는 얼마든지 위치를 원하는 대로 변경할 수 있음을 기억하자.

왼쪽 구역을 생각했을 때 왼쪽을 바라보는 미어캣들이 최대한 많이 바라볼 수 있게 하려면,

오른쪽을 바라보는 미어캣들을 제일 작은 미어캣부터 왼쪽에서 오른쪽으로 오름차순으로 배치
왼쪽을 바라보는 미어캣들을 가장 큰 미어캣부터 오른쪽에서 왼쪽으로 내림차순 배치

이번엔 오른쪽 구역을 생각해보자.

왼쪽을 바라보는 미어캣들을 가장 작은 미어캣부터 오른쪽에서 왼쪽으로 오름차순 배치
오른쪽을 바라보는 미어캣들을 가장 큰 미어캣부터 왼쪽에서 오른쪽으로 내림차순 배치

해당 기준점을 처음부터 끝까지 탐색하면 된다.

기준점은 N개이고, 각 기준점에 대한 망을 볼 수 있는 미어캣의 최대 갯수를 확인하는데는 N의 연산이 필요하다.
따라서 $O(N^2)$에 해결 가능하다.

코드

#include <bits/stdc++.h>

#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define For(i, n) for(int i=0; i<n; ++i)
#define For1(i, n) for(int i=1; i<=n; ++i)
#define For2(i, a, b) for(int i=(a); i<=(b); ++i)
#define ft first
#define sd second
#define Get(i, v) get<i>(v)

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ti3 = tuple<int, int, int>;
using tl3 = tuple<ll, ll, ll>;

const int INF = numeric_limits<int>::max();
const ll LNF = numeric_limits<ll>::max();

void solve() {
    int n; cin >> n;
    vector<int> l, r;
    vector<char> v;
    For(i,n) {
        int x; char d; cin >> x >> d;
        v.emplace_back(d);
        if(d=='L') l.emplace_back(x);
        else r.emplace_back(x);
    }
    sort(all(l)); sort(all(r));

    vector<int> a(n);
    int ans = 0;
    For(i,n+1) {
        int rdx=0, ldx=0;
        for(int j=0; j<i; j++) {
            if(v[j] == 'R') a[j] = r[rdx++];
        }
        for(int j=n-1; j>=i; j--) {
            if(v[j] == 'R') a[j] = r[rdx++];
            if(v[j] == 'L') a[j] = l[ldx++];
        }
        for(int j=0; j<i; j++) {
            if(v[j] == 'L') a[j] = l[ldx++];
        }

        int res=0, h=0;
        for(int j=0; j<n; j++) {
            if(v[j] == 'L' && h < a[j]) res++;
            h = max(h, a[j]);
        }
        h = 0;
        for(int j=n-1; j>=0; j--) {
            if(v[j] == 'R' && h < a[j]) res++;
            h = max(h, a[j]);
        }
        ans = max(ans, res);
    }
    cout << ans << endl;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int tc = 1;
//    cin >> tc;
    while(tc--) {
        solve();
//        cout << solve() << endl;
    }


    return 0;
}

D. 이진 검색 트리 복원하기

val이라는 값을 갖고 있는 노드를 생각해보자.
해당 노드의 왼쪽 자식은 val보다 작아야 하고, 오른쪽 자식은 val보다 커야 한다.
문제에서 주어지는 높이에 들어가는 모든 값들이 해당 규칙에 알맞게 들어갈 수 있어야 한다.
이를 이용해서 문제를 풀어보자.

각 노드들에는 min, max 값을 갖고 있는데 이 말은 해당 노드에 들어가는 값은 min이상 max이하이어야 한다는 뜻이다.
현재 queue에는 현재 높이에 만들 수 있는 노드들이 들어있다고 가정하자.(여기서 만들 수 있는 노드라는 건 이전 높이에 존재하는 노드들의 자식 노드들을 모두 넣었다는 의미다. 이때 자식 노드들에는 자신의 부모노드로부터 내려온 min, max값을 가지고 있다.)
이번 높이 h에 들어가야 하는 값들을 보았을 때, 모든 값들을 알맞게 넣는다. 그리고 생성된 노드들에 대해 자식 노드들을 다시 queue에 넣어준다.

이런 식으로 반복하였을 때 모든 값들이 무리없이 노드에 들어갈 수 있다면 이진트리 복원이 가능한 것이다.
초기값은 min = -INF, max = INF으로 하고 넣으면 된다.

구현할 때 주의할 점은 다음 높이로 넘어갈 때 이전 높이의 노드들은 남아있다면 다 삭제해줘야 한다.

후기

구현의 범위가 다양할 것 같다.
해결 아이디어의 난이도보다는 구현적인 아이디어가 좀 더 필요했던 문제였던 것 같다.

코드

#include <bits/stdc++.h>

#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define For(i, n) for(int i=0; i<n; ++i)
#define For1(i, n) for(int i=1; i<=n; ++i)
#define For2(i, a, b) for(int i=(a); i<=(b); ++i)
#define ft first
#define sd second
#define Get(i, v) get<i>(v)

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ti3 = tuple<int, int, int>;
using tl3 = tuple<ll, ll, ll>;

const int INF = numeric_limits<int>::max();
const ll LNF = numeric_limits<ll>::max();

struct Node {
    int val = -1;
    int idx = -1;
    int _min = -INF, _max = INF;
    Node *l = NULL, *r = NULL;

    Node() {}
    Node(int __min, int __max) :  _min(__min), _max(__max) {}
//    Node(int _val, int __min, int __max) : val(_val), _min(__min), _max(__max) {}
};


void solve() {
    priority_queue<array<int,3>, vector<array<int,3>>, greater<>> pq; // (높이, 값)
    int n; cin >> n;
    For(i,n) {
        int a, h; cin >> a >> h;
        pq.push({h,a,i});
    }

    vector<Node*> ans(n);
    queue<Node*> nodes;
    nodes.emplace(new Node());
    for(int h=1; h<=n && !pq.empty(); h++) {
        int sz = (int)nodes.size();
        while(!pq.empty() && pq.top()[0] == h) {
            auto [_,a,i] = pq.top(); pq.pop();
            bool flag = false;
            while(sz > 0) {
                auto node = nodes.front(); nodes.pop();
                sz--;
                if(node->_min <= a && a <= node->_max) {
                    flag = true;
                    node->val = a;
                    node->idx = i+1;
                    node->l = new Node(node->_min, a-1);
                    node->r = new Node(a+1, node->_max);
                    nodes.emplace(node->l);
                    nodes.emplace(node->r);
                    ans[i] = node;
                    break;
                }
            }
            if(!flag) {
                cout << -1 << endl;
                return;
            }
        }
        while(sz>0) {
            nodes.pop();
            sz--;
        }
    }

    For(i,n) {
        Node *node = ans[i];
        cout << node->l->idx << ' ' << node->r->idx << endl;
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int tc = 1;
//    cin >> tc;
    while(tc--) {
        solve();
//        cout << solve() << endl;
    }


    return 0;
}

E. 지금 자면 꿈을 꾸지만

시간의 범위가 $10^4$ 이고 n,a,b의 범위 또한 $10^2$이므로, $10^8$에 완전탐색으로 풀 수 있는 문제다.

tm 시간을 정하고 tm부터 tm+bx까지 잔다고 가정하자.

0~tm : a 완료 시간으로 최대한 과제를 마무리한다.
tm~tm+bx : 수면
tm+bx : a-x 완료 시간으로 최대한 과제를 마무리한다.

x는 0 ~ a-1 의 범위이고, 각 tm과 x가 주어질 때마다 완료가능한 과제 수를 세는데 n번 연산이 필요하다.
따라서 $O(10^8)$에 해결할 수 있다.

후기

매우 간단한 브루트포스 문제이지만, 막상 대회 때에는 생각이 이리저리 꼬여서 구현이 안 됐다.
결국 내가 잡고 있다가는 계속 꼬이기만 할 것 같아서 다른 팀원에게 넘기고 내가 다른 문제를 풀었다.
결국 팀원이 풀어줬지만 이 문제를 제대로 빠르게 풀었다면 시간 단축 및 자신감 상승에 도움이 됐을 것이다.

제대로 생각하고 들어갔어야 하는데 조급한 마음에 풀이가 대충 나오자마자 구현에 들어가버린 것이 실수였다.
거기서 패치를 붙이듯이 코드를 덕지덕지 붙여버리니 풀릴 문제도 안 풀리게 되고 생각이 꼬이게 되었다. 반성해야 할 부분이다.

코드

#include <bits/stdc++.h>

#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define For(i, n) for(int i=0; i<n; ++i)
#define For1(i, n) for(int i=1; i<=n; ++i)
#define For2(i, a, b) for(int i=(a); i<=(b); ++i)
#define ft first
#define sd second
#define Get(i, v) get<i>(v)

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ti3 = tuple<int, int, int>;
using tl3 = tuple<ll, ll, ll>;

const int INF = numeric_limits<int>::max();
const ll LNF = numeric_limits<ll>::max();

void solve() {
    int n, a, b; cin >> n >> a >> b;
    vector<int> v(n);
    For(i,n) cin >> v[i];
    sort(all(v));
    int ans=0;
    for(int tm=0; tm<=1e4; tm++) {
        for(int x=0; x<a; x++) {
            int res = 0;
            int idx=0, curtm=a;
            while(idx<n && curtm <= tm) {
                if(curtm <= v[idx]) {
                    res++;
                    curtm += a;
                }
                idx++;
            }
            curtm = tm + b*x + a-x;
            while(idx<n) {
                if(curtm <= v[idx]) {
                    res++;
                    curtm += a-x;
                }
                idx++;
            }
            ans = max(ans, res);
        }
    }
    cout << ans << endl;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int tc = 1;
//    cin >> tc;
    while(tc--) {
        solve();
//        cout << solve() << endl;
    }


    return 0;
}

G. 석고 모형 만들기

다양한 방식으로 해결이 가능할 것 같긴 한데, 필자는 union-find 로 풀었다.
결국 3가지 타입의 원기둥이 들어가면 1x1x1 정육면체은 최대 8개의 작은 조각 단위로 쪼개질 수 있다.

따라서 각 1x1x1 정육면체를 0.5x0.5x0.5 정육면체 8개로 쪼갰다.
그럼 총 $R \times C \times 8$ 개의 정육면체가 나온다. R과 C는 최대 200개이기 때문에 $3.2 \times 10^5$ 개가 나오므로 가능하다.

먼저 (i,j) 위치의 1x1x1 정육면체를 보자.
해당 정육면체의 오른쪽 면에 인접한 0.5x0.5x0.5 정육면체들은 각각 오른쪽 정육면체의 왼쪽면에 접한 0.5x0.5x0.5 정육면체들과 merge 시켜준다.
아래쪽 면에 인접한 0.5x0.5x0.5 정육면체들은 각각 아래쪽 정육면체의 위쪽면에 접한 0.5x0.5x0.5 정육면체들과 merge 시켜준다.

다음으로 (i,j) 1x1x1 정육면체에 어떤 원기둥이 들어왔는지 확인해보자.

H 일때,
정육면체 내부의 가로축 방향으로 인접한 0.5x0.5x0.5 정육면체들을 merge시켜준다.
I 일때,
정육면체 내부의 세로축 방향으로 인접한 0.5x0.5x0.5 정육면체들을 merge시켜준다.
O 일때,
정육면체 내부의 바닥에 수직인 방향으로 인접한 0.5x0.5x0.5 정육면체들을 merge시켜준다.

모든 $R \times C \times 8$ 개의 정육면체들을 탐색하면서 총 몇개의 그룹이 나왔는지를 확인하고 출력하면 된다.

후기

대회에서 보았을 때는 무지막지한 구현 및 시뮬레이션 문제라고 생각하고 넘겼다.
물론 실제로도 구현이었지만, union-find를 사용하니 생각보다 많은 구현이 필요하지는 않았다.
시간만 충분히 들였다면 풀 수 있는 문제였으나, 다른 문제들에 너무 발을 잡히고 해당 문제는 당연히 무지막지한 구현이라 생각하여 쉽게 넘긴 것이 패착이었다.

코드

#include <bits/stdc++.h>

#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define For(i, n) for(int i=0; i<n; ++i)
#define For1(i, n) for(int i=1; i<=n; ++i)
#define For2(i, a, b) for(int i=(a); i<=(b); ++i)
#define ft first
#define sd second
#define Get(i, v) get<i>(v)

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ti3 = tuple<int, int, int>;
using tl3 = tuple<ll, ll, ll>;

const int INF = numeric_limits<int>::max();
const ll LNF = numeric_limits<ll>::max();

vector<int> parent;

int find(int i) {
    if(i == parent[i]) return i;
    return parent[i] = find(parent[i]);
}
bool merge(int a, int b) {
    a = find(a), b = find(b);
    if(a == b) return false;
    parent[b] = a;
    return true;
}

void solve() {
    int r, c; cin >> r >> c;
    vector<vector<char>> grid(r+2, vector<char>(c+2, 0));
    For1(i,r) For1(j,c) cin >> grid[i][j];

    parent = vector<int>(r*c*8 + 1);
    for(int i=1; i<=r*c*8; i++) parent[i] = i;

    auto get_num = [&](int i, int j) {
        int num = (i-1)*c + j;
        return (num-1)*8;
    };

    for(int i=1; i<=r; i++) {
        for(int j=1; j<=c; j++) {
            // 위-아래
            if(i < r) {
                int up = get_num(i,j);
                int down = get_num(i+1,j);
                merge(up+3, down+1);
                merge(up+4, down+2);
                merge(up+7, down+5);
                merge(up+8, down+6);
            }

            // 좌-우
            if(j < c) {
                int left = get_num(i,j);
                int right = get_num(i,j+1);
                merge(left+2, right+1);
                merge(left+4, right+3);
                merge(left+6, right+5);
                merge(left+8, right+7);
            }

            int num = get_num(i,j);
            if(grid[i][j] == 'H') {
                merge(num+1, num+2);
                merge(num+3, num+4);
                merge(num+5, num+6);
                merge(num+7, num+8);
            }
            else if(grid[i][j] == 'I') {
                merge(num+1, num+3);
                merge(num+2, num+4);
                merge(num+5, num+7);
                merge(num+6, num+8);
            }
            else {
                merge(num+1, num+5);
                merge(num+2, num+6);
                merge(num+3, num+7);
                merge(num+4, num+8);
            }
        }
    }

    set<int> st;
    for(int i=1; i<=r*c*8; i++) {
        st.insert(find(i));
    }

    cout << st.size() << endl;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int tc = 1;
//    cin >> tc;
    while(tc--) {
        solve();
//        cout << solve() << endl;
    }


    return 0;
}

H. 만보기 대행 서비스

케이스를 나눠야 풀 수 있었던 문제였다.

위치가 양수인 보관함들 끼리는 결국 맨 끝 양수 보관함까지 갔다오는 것이 무조건 이득이고, 반대로 음수도 마찬가지다.
그렇다면 우리는 맨 왼쪽과 맨 오른쪽의 휴대폰을 언제 수집하고 언제 반납할 것인 지에 대한 모든 케이스를 해보면 될 것이다.

왼쪽 끝의 위치를 l, 오른쪽 끝의 위치를 r이라 하자.
또한 len = r-l 이라 하자.
여기서 a,b는 l 또는 r이다.

원점 - a 수집 - a 반납 - b 수집 - b 반납 - 원점
- $dist(0,a) + D + dist(a,b) + D + dist(b,0)$ 만큼 이동.
- 정리하면, $2 \times len + 2 \times D$
원점 - a 수집 - b 수집 - a 반납 - b 반납 - 원점
- $dist(0,a) + max(D/2,dist(a,b)) + max(D/2,dist(b,a)) + dist(a,b) + dist(b,0)$
- 정리하면, $2 \times len + max(D,2 \times len)$
원점 - a 수집 - b 수집 - b 반납 - a 반납 - 원점
- $dist(0,a) + dist(a,b) + D + dist(b,a) + dist(a,0)$
- 정리하면, $2 \times len + D + 2 \times dist(0,a)$

\[dist(0,a) + max(D/2,dist(a,b)) + max(D/2,dist(b,a)) + dist(a,b) + dist(b,0)\]

후기

케이스를 잘 나눴어야 하는데 케이스 하나를 놓치기 쉬웠던 문제이다.
결국 l,r을 각각 언제 수집하고 언제 반납하는 지를 나눠야 한다.
항상 수집한 후에 반납할 수 있으니, 수집과 반납은 정해져 있으므로 $Comb(4,2) = 6$ 이다.
여기서 l과 r을 a,b라는 변수로 넣으면 각 케이스마다 a,b를 l,r 또는 r,l로 매칭해볼 수 있으므로 총 3개의 케이스만 생각해 보면 될 것이다.

코드

#include <bits/stdc++.h>  
  
#define endl "\n"  
#define all(v) (v).begin(), (v).end()  
#define For(i, n) for(int i=0; i<n; ++i)  
#define For1(i, n) for(int i=1; i<=n; ++i)  
#define For2(i, a, b) for(int i=(a); i<=(b); ++i)  
#define ft first  
#define sd second  
#define Get(i, v) get<i>(v)  
  
using namespace std;  
using ll = long long;  
using ld = long double;  
using pii = pair<int, int>;  
using pll = pair<ll, ll>;  
using ti3 = tuple<int, int, int>;  
using tl3 = tuple<ll, ll, ll>;  
  
const int INF = numeric_limits<int>::max();  
const ll LNF = numeric_limits<ll>::max();  
  
ll solve() {  
    ll n, d; cin >> n >> d;  
    ll l = 0, r = 0;  
    For(i,n) {  
        ll x; cin >> x;  
        l = min(l, x);  
        r = max(r, x);  
    }  
    ll len = r-l;  
    ll ans = LNF;  
    ans = min(ans, 2*len + 2*d);  
    ans = min(ans, 2*len + max(d, 2*len));  
    ans = min(ans, 2*len + d + 2*min(abs(l),abs(r)));  
    return ans;  
}  
  
int main(void) {  
    ios_base::sync_with_stdio(false);  
    cin.tie(nullptr);  
    cout.tie(nullptr);  
  
    int tc = 1;  
//    cin >> tc;  
    while(tc--) {  
//        solve();  
        cout << solve() << endl;  
    }  
  
  
    return 0;  
}

J. 동전 쌍 뒤집기

stack을 이용해서 풀 수 있는 문제다.

stack에는 현재 뒤집어야 하는 동전들만 넣는다고 가정하자.
현재 들어오는 동전과 stack의 top에 있는 동전의 면이 같다면 우리는 뒤집을 수 있다. 뒤집고 나면 stack의 top을 pop해준다.
이때 해당 top의 동전의 인덱스를 l, 현재 들어오는 동전의 인덱스를 r이라 한다면 우리는 l과 r 사이에 있는 모든 동전들을 뒤집어 주어야 모든 동전을 H로 바꿀 수 있다.
우리는 짝수개의 동전만 뒤집기 떄문에 l~r 의 동전의 갯수는 항상 짝수이다. (결국 stack 에서 l과 r사이의 사라진 동전들은 뒤집은 동전들이므로)

따라서 ans += (l~r 사이의 동전의 갯수) / 2 를 해줘야 한다.

코드

#include <bits/stdc++.h>

#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define For(i, n) for(int i=0; i<n; ++i)
#define For1(i, n) for(int i=1; i<=n; ++i)
#define For2(i, a, b) for(int i=(a); i<=(b); ++i)
#define ft first
#define sd second
#define Get(i, v) get<i>(v)

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ti3 = tuple<int, int, int>;
using tl3 = tuple<ll, ll, ll>;

const int INF = numeric_limits<int>::max();
const ll LNF = numeric_limits<ll>::max();

void solve() {
    int n; cin >> n;
    string s; cin >> s;
    stack<pair<char,int>> st;
    ll ans = 0;
    for(int i=0; i<n; i++) {
        if(s[i] == 'H' && st.empty()) continue;
        if(!st.empty() && st.top().first == s[i]) {
            ans += (i-st.top().second+1)/2;
            st.pop();
        }
        else st.emplace(s[i], i);
    }
    if(st.empty()) cout << ans << endl;
    else cout << -1 << endl;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int tc = 1;
    cin >> tc;
    while(tc--) {
        solve();
//        cout << solve() << endl;
    }


    return 0;
}

K. 나무 심기

케이스를 나눠야 하는 문제였다.

각 씨앗별 연결된 간선의 갯수를 모두 세면 각 간선 당 2번 카운트되기 때문에 카운트된 간선의 갯수는 짝수다.
이때 복숭아 씨앗이 홀수개이면, 복숭아 씨앗들의 간선 갯수는 홀수가 된다. (홀수 x 홀수 이므로)
사과 씨앗은 항상 간선의 갯수가 짝수개 이므로 두 종류의 씨앗의 간선 갯수들을 합치면 홀수가 된다.
하지만 이것은 모순이므로 복숭아 씨앗은 항상 짝수개이어야 한다.

이 다음부터는 사실상 많이 그려보고 생각해 보면서 조건을 나눠야 한다.

b가 0이라면,
- a%3 == 1이라면,
  1, 4, 7, 11… 들은 서로 인접한 2x2 정사각형들을 대각선으로 이어서 붙이면 된다.
  a = 11 일 떄는 아래와 같이 된다.
```
1
2
3
4
  OO...  
  OOO.  
  .OOO  
  ..OO
```
- a%3 == 2이라면,
```
1
2
3
  OOO  
  O.O  
  OOO
```
  위와 같이 생긴 격자에 a%3 == 1과 마찬가지로 우측하단에 대각선 방향으로 2x2 정사각형들을 대각선으로 이어붙이면 된다.
  기본 모형이 8개부터 시작하므로 a는 8 이상이어야 한다.
- a%3 == 0이라면,
```
1
2
3
4
  OOOO  
  O..O  
  O..O  
  OOOO  
```
  마찬가지로 위와 같이 생긴 격자에 2x2 정사각형들을 우측 하단 대각선 방향으로 이어붙이면 된다.
  기본 도형이 12개부터 시작이므로 a는 12 이상이어야 한다.
b가 0이 아니라면,
사실상 b가 2이상인 짝수인 건데, 이러면 일직선으로 O을 나열한 다음에, 홀수가 필요한 만큼 위 아래로 씨앗을 심으면 된다.
예를 들어,
```
1
2
3
  .O.O......  
  OOOOOOOOOO  
  ..O.O.....
```
이런 식으로 하면 된다.
좀 더 자세히 얘기하면 위 아래로 번갈아가면서 씨앗을 심을 애들을 b2개라고 하자.
$b = b2 \times 2 + 2$ 가 된다. 따라서 가로의 길이는 $1+b2+a+1$ 이 된다.

후기

조건 분기 및 해 구성하기라 정말 까다로웠다.
많은 케이스들을 생각해야 했고 반례가 나오기 정말 쉬웠던 문제였던 것 같다.
이런 유형은 정말 연습만이 답인 것 같다.

코드

#include <bits/stdc++.h>

#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define For(i, n) for(int i=0; i<n; ++i)
#define For1(i, n) for(int i=1; i<=n; ++i)
#define For2(i, a, b) for(int i=(a); i<=(b); ++i)
#define ft first
#define sd second
#define Get(i, v) get<i>(v)

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ti3 = tuple<int, int, int>;
using tl3 = tuple<ll, ll, ll>;

const int INF = numeric_limits<int>::max();
const ll LNF = numeric_limits<ll>::max();

void print(vector<vector<char>> &grid) {
    cout << "YES\n";
    int r = grid.size(), c = grid.front().size();
    cout << r << ' ' << c << endl;
    for(int i=0; i<r; i++) {
        for(int j=0; j<c; j++) {
            cout << grid[i][j];
        }
        cout << endl;
    }
}

void solve() {
    int a, b; cin >> a >> b;
    if(b%2) {
        cout << "NO" << endl;
        return;
    }
    if(b == 0) {
        if(a%3 == 1) {
            int r = a/3+1;
            vector<vector<char>>grid(r, vector<char>(r,'.'));
            grid[0][0] = 'O';
            for(int i=1; i<r; i++) {
                grid[i][i] = grid[i][i-1] = grid[i-1][i] = 'O';
            }
            print(grid);
        }
        else if(a >= 8 && a%3 == 2) {
            int r = 3 + (a-8)/3;
            vector<vector<char>> grid(r, vector<char>(r,'.'));
            for(int i=0; i<3; i++) {
                for(int j=0; j<3; j++) {
                    if(i==1 && j==1) continue;
                    grid[i][j] = 'O';
                }
            }
            for(int i=3; i<r; i++) {
                grid[i][i] = grid[i][i-1] = grid[i-1][i] = 'O';
            }

            print(grid);
        }
        else if(a >= 12 && a%3 == 0) {
            int r = 4 + (a-12)/3;
            vector<vector<char>> grid(r, vector<char>(r,'.'));
            for(int i=0; i<4; i++) {
                for(int j=0; j<4; j++) {
                    if(i==0 || i==3 || j==0 || j==3) grid[i][j] = 'O';
                }
            }
            for(int i=4; i<r; i++) {
                grid[i][i] = grid[i][i-1] = grid[i-1][i] = 'O';
            }

            print(grid);
        }
        else {
            cout << "NO\n";
        }
    }
    else {
        int b2 = b/2-1;
        int loc=-1;
        vector<vector<char>> grid(3,vector<char>(a+b2+2,'.'));
        for(int i=0; i<grid[1].size(); i++) {
            grid[1][i] = 'O';
            if(b2>0 && i!=0 && i!=grid[i].size()-1) {
                grid[1+loc][i] = 'O';
                loc *= -1;
                b2--;
            }
        }

        print(grid);
    }

}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int tc = 1;
//    cin >> tc;
    while(tc--) {
        solve();
//        cout << solve() << endl;
    }


    return 0;
}

UCPC 2024 예선 후기 및 풀이

C. 미어캣

코드

D. 이진 검색 트리 복원하기

후기

코드

E. 지금 자면 꿈을 꾸지만

후기

코드

G. 석고 모형 만들기

후기

코드

H. 만보기 대행 서비스

후기

코드

J. 동전 쌍 뒤집기

코드

K. 나무 심기

후기

코드

Leave a comment

You may also enjoy

백준 17407 - 괄호 문자열과 쿼리

백준 28219 - 주유소

백준 1432 - 그래프 수정

백준 1498 - 주기문