AtCoder Beginner Contest 218 A부터 E까지 업솔빙

AtCoder Beginner Contest 218 A부터 E까지 업솔빙

AtCoder가 코드포스보다 높은 레이팅으로 쳐주는 이유를 이 대회를 풀면서 나왔다. 분명 800가량 퍼포먼스가 나와서 현재 레이팅이 600인 상황이었기에 조금이나마 오를거라고 생각했는데, -7점을 받았다. 도대체 무슨 기준일까? 이번 대회에서는 D번 문제에서 시간을 많이 써서 E번 문제를 풀다가 포기했다. E번 문제는 딱보면 무슨 알고리즘인줄 알았지만 그것을 응용하는 문제를 여기서 처음 만나서 그런지 헤맸다. 그리고 C번 문제는 일단 영어를 이해 못했고, 두번째로 솔직히 접근 방법조차 이해가 안됐다.
이번 대회에서 배운 것은

1. 크루스칼 알고리즘 구현 복습 & 응용 문제 풀기
2. 행렬의 전치 알고리즘으로 구현하기
3. 도형의 평행이동 함수로 구현하기

문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다.

A - Weather Forecast (*7)

접기/펼치기

문제 설명
내일부터 일주일간 날씨 상태를 나타내는 문자열 $S$가 주어진다.
만약 $S$의 $i$번째 문자가 o이면 이 일주일 중 $i$번째 날은 맑음이고, 문자가 x이면 그 날은 비이다.

$N$번째 날이 맑음인지 알아내라.

문제 해설
$N$번째 날은 $S[N - 1]$번째 문자열을 확인하면 된다. 왜냐하면 첫번째 날이 $S[0]$ 기준이기 때문이다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cin.tie(0);
    int n; cin >> n;
    string s; cin >> s;
    cout << (s[n - 1] == 'o' ? "Yes" : "No");
    return 0;
}

B - qwerty (*14)

접기/펼치기

문제 설명
$1$부터 $26$까지 정수로 이루어진 $26$개 정수 배열 $P = (P_1, P_2, ...., P_26)$ 이 주어진다.
다음 조건을 만족하는 길이가 $26$인 문자열 $S$를 출력하라.

• 모든 $i (1 \le i \le 26)$에 대해서 $S$의 $i$번째 문자는 알파벳 $P_i$번째 순서에 있는 알파벳이다.

문제 해설
$1$번째가 $a$이고, $2$번째가 $b$이고, ...$26$번째가 $z$이기 때문에 $n$번째라고 하면 $n + 'a'$ 에다가 $1$을 빼준 값을 char자료형으로 형 변환 한 다음에 출력하면 된다. $1$을 뺀 이유는 $1$을 빼지 않으면 $1$번째 문자가 $b$가 되기 때문이다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cin.tie(0);
    for(int i = 0; i < 26; i++){
        int n; cin >> n;
        cout << (char)(n - 1 + 'a');
    }
    return 0;
}

C - Shapes (*1012)

접기/펼치기

문제 설명
직사각형 격자로 이루어진 두 모양 $S$와 $T$가 주어진다.
이 모양을 $90$도로 돌리고, 평행이동 시켜서 정확히 일치하는지 아닌지 판단하라.

문제 해설
문제는 간단한데 코드 구현하는게 상당히 빡센 문제라고 생각한다. 일단 배열에 있는 값을 90도로 돌리고, 평행이동 하는 코드를 작성해야 한다. 이때 모든 좌표를 옮기기에는 시간이 너무 많이 걸리기 때문에 "#" 모양이 있는 위치의 좌표만 담아서 관리하면 편하고, set에 넣어서 사용한다. 이 자료구조를 사용하는 이유는 등호 연산을 지원하기 때문이다. set에서 등호연산을 사용하면 두 set에 있는 모든 원소가 같으면 true를, 아니면 false를 출력한다.

배열 전체를 90도 회전하는 것은 행렬의 전치를 생각하면 쉽게 이해할 수 있다. 안그러면 그냥 좌표를 찍고, 그 좌표를 90도 돌린 상태의 좌표를 비교하면 공식이 나오게 된다. 그 공식을 사용해서 전체 모습을 뒤집는다면 쉽게 구현 할 수 있다.

한 모양을 전체 평행이동 하는 것은 기준점을 잡아야 한다. 우리는 컴퓨터 2차원 배열을 기준으로 왼쪽 위를 $(0, 0)$이라고 정의해서 사용했다. 그러면 한 모양에서 가장 왼쪽, 가장 위쪽에 있는 점의 좌표를 찾고, 모든 점을 그 좌표 만큼 뺀다면 맨 왼쪽 위가 $(0, 0)$으로 모든 좌표가 평행이동 된다.

한 모양을 총 4번 돌리고, 평행이동 한 모양을 나머지 모양과 비교해서 한번이라도 정확하면 true를, 그렇지 않으면 false를 출력한다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
int n; 

void trans(set<pii>& t){
    set<pii> s;
    int mx = 3000, my = 3000;
    for(auto x : t) mx = min(mx, x.first), my = min(my, x.second);
    for(auto x : t) s.insert({x.first - mx, x.second - my});
    t = s;
}

void rot(set<pii>& t){
    set<pii> s;
    for(auto x : t) s.insert({n - 1 - x.second, x.first});
    t = s;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cin.tie(0);
    set<pii> a, b;
    cin >> n;
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){
        char c; cin >> c;
        if(c == '#') a.insert({i, j});
    }
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){
        char c; cin >> c;
        if(c == '#') b.insert({i, j});
    }

    trans(a);
    for(int i = 0; i < 4; i++){
        rot(b);
        trans(b);
        if(a == b){
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
    return 0;
}

D - Rectangles (*715)

접기/펼치기

문제 설명
2차원 좌표계에 $N$개 점이 있다. 이 점은 각각 $1, 2, ..., N$이라고 정의되어 있으며 점 $i (1 \le i \le N)$은 좌표 $(x_i, y_i)$에 위치한다.

주어잔 좌표만 사용해서 $x$축과 $y$축 모두 평행한 직사각형을 몇개 만들 수 있을까?

문제 해설
이 문제는 사실 내가 엄청 돌아서 푼 문제였다. 내가 처음 생각한 방법은 2개 이상의 점을 가진 행을 두개 선택하고, 그 행에서 한 열에 2개 점이 존재한 열의 개수를 세고, 그 개수에 조합 공식을 적용해서 풀었다. 이렇게 하니까 $N$은 $2000$보다 작지만 $x, y$의 범위가 $10^9$이기 때문에 좌표 압축을 사용해야 했고 좀 귀찮았지만 결국 해결했다.

그런데 이 문제의 의도는 다른 곳에 있었다. 대각선 좌표 2개를 고른다면 나머지 두 좌표는 직사각형이기 때문에 고정된다는 점을 이용했다. 즉 $N \le 2000$이기 때문에 완전탐색으로 좌표 2개를 고른다. 이때 첫번째 좌표는 두번째 좌표보다 작아야 한다. 이렇게 안하면 직사각형이 고정이 안된다. 이렇게 조건에 맞는 두 좌표를 찾았다면 나머지 좌표를 찾아야 하는데 그냥 이분 탐색을 사용하면 된다. 이 두 점이 모두 존재한다면 직사각형을 만들수 있다는 의미이므로 답에 1을 추가한다.

여기서 유용한 것은 pair가 들어있는 배열도 binary_search가 사용가능하다는 점이다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cin.tie(0);
    int n; cin >> n;
    vector<pair<int, int>> v(n);
    for(auto& x : v) cin >> x.first >> x.second;
    sort(v.begin(), v.end());
    int ans = 0;
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){
        if(v[i].first < v[j].first && v[i].second < v[j].second){
            if(binary_search(v.begin(), v.end(), make_pair(v[i].first, v[j].second)) && 
            binary_search(v.begin(), v.end(), make_pair(v[j].first , v[i].second))) ans++;
        }
    }
    cout << ans;
    return 0;
}

E - Destruction (*1004)

접기/펼치기

문제 설명
$N$개 정점과 $M$개 간선으로 이루어져 있는 무방향 그래프가 주어진다.
정점은 $1$부터 $N$까지, 간선은 $1$부터 $M$까지 번호가 붙여있고 간선 $i$는 정점 $A_i$와 $B_i$를 연결한다.

진수는 이 그래프에서 0개 혹은 그 이상 간선을 지울 것이다.

간선 $i$를 제거할때, 만약 $C_i \ge 0$ 이면 보상 $C_i$를 받고, 만약 $C_i < 0$이면 비용 $|C_i|$이 차감한다.
간선을 제거하고 나서 모든 정점이 연결되어 있을 때 얻을 수 있는 진수의 최대 보상을 구하라.

문제 해설
보상이 큰 간선을 제거해야 한다. 반대로 생각하면 보상이 작은 간선을 남겨야 하는데 모든 정점을 서로 연결해야 한다. 그렇다. 최소 스패닝 트리 문제다. 바로 떠오르지 않는다면 공부하러 가자. 이해하기 의외로 쉽고 자주 사용한다.

최소 스패닝 트리 문제는 보통 크루스칼 알고리즘을 사용하고 이 문제는 이 크루스칼 알고리즘에 아주 약간의 응용이 들어간다. 크루스칼 알고리즘을 사용하면 최소 간선을 연결하고 그 뒤에 중복으로 나오는 알고리즘은 DSU에 포함하지 않는다. 즉 DSU에서 MERGE안되는 간선은 바로 제거해야 하는 간선이라는 뜻이다. 그런데 무작정 제거하면 답이 안된다. 이때 음수인 간선은 제거하면 오히려 손해가 된다. 음수인 간선을 제거하면 오히려 비용이 부과되므로 안 제거하는게 이득이다. 문제에서 모든 간선이 연결되어 있기만 하면 된다고 했지 정점간 간선이 오직 1개만 있어야 한다는 조건은 달지 않았다. 따라서 간선을 제거해야 하는 상황이 올때 간선이 양수인 경우에만 보상에 더하고 그 값을 출력한다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int root[200005];
int find(int x){
    if(x == root[x]) return x;
    return root[x] = find(root[x]);
}

bool merge(int u, int v){
    u = find(u), v = find(v);
    if(u == v) return true;
    root[u] = v;
    return false;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cin.tie(0);
    int n, m; cin >> n >> m;
    for(int i = 0; i <= n; i++) root[i] = i;
    priority_queue<pair<int, pair<int, int>>> pq;
    for(int i = 0; i < m; i++){
        int a, b, c; cin >> a >> b >> c;
        pq.push({-c, {a, b}});
    }

    long long ans = 0;
    while(pq.size()){
        auto node = pq.top();
        pq.pop();
        int cost = -node.first;
        int x = node.second.first, y = node.second.second;
        if(merge(x, y)){
            if(cost > 0) ans += cost;
        }
    }
    cout << ans;
    return 0;
}