AtCoder Beginner Contest 212 A부터 D까지 업솔빙

AtCoder Beginner Contest 212 A부터 D까지 업솔빙

D번까지 다 푼 대회이다. 내 1차 목표는 Atcoder D번까지 안정적으로 푸는 실력을 갖추는 것이기 때문에 매우 만족스럽다. C번 문제에서 조금 헤맸지만 정해와는 다른 방법을 사용해서 어찌어찌 풀었고, 정해에서 보여준 아이디어또한 매우 좋은것 같아서 배울점이 많은 문제였다. 상대적으로 D번문제는 아이디어를 조금 더 보는 문제였고, 쉽게 떠올라서 바로 풀었다. 나도 좀 더 어려운 문제를 이런 식으로 풀수 있길 바라면서 글 시작하겠다. 이번 대회에서 배운 것은

1. 우선순위 큐 min heap설정하기
2. 그리디 알고리즘 기초 감잡기

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

A - Alloy (*5)

접기/펼치기

문제 설명
새로운 금속을 만들기 위해 금 $A$그램과 은 $B$그램을 녹여서 섞었다. $(0 \le A, B, 0 < A + B)$

이 금속은 순수한 금일까? 순수한 은일까? 혹은 합금일까?

일반적으로 다음과 같은 방식으로 정한다.

• $0 < A, B = 0$이면 순수한 금이다.
• $0 = A, 0 < B$이면 순수한 은이다.
• $0 < A, 0 < B$이면 합금이다.

문제 해설
조건문 3개. 끝.

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int a, b; cin >> a >> b;
    if(b == 0) cout << "Gold";
    else if(a == 0) cout << "Silver";
    else cout << "Alloy";
    return 0;
}

B - Weak Password (*64)

접기/펼치기

문제 설명
4자리 정수 PIN숫자 $X_1X_2X_3X_4$가 주어진다. 이 숫자는 0으로 시작할 수 있다. 다음 조건중 하나라도 만족하면 PIN숫자가 취약하다고 한다.

• 4개 숫자 모두 같은 숫자이다.
• $1 \le i \le 3$ 인 정수 $i$에 대해서 $X_i$ 다음에 $X_{i + 1}$가 나온다. 즉 $0 \le j \le 8$ 인 $j$에 대해서 $j$다음에 $j + 1$이 나온다. 그리고 $9$다음에 $0$이 나온다.

주어진 PIN 숫자가 취약하면 Weak를 출력하고 아니면 Strong을 출력한다.

문제 해설
두개 조건을 각각 따로따로 확인한 다음에 두 조건중 하나라도 만족하면 Weak, 아니면 Strong을 출력한다. 이때 $9$다음에 $0$이 나온다는 조건때문에 $X_i$ 에 1을 더한 값을 $X_{i + 1}$과 비교할 때, 10을 나눈 나머지 값으로 비교해야 한다.

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int a[4];
    for(int i = 0; i < 4; i++){
        char c; cin >> c;
        a[i] = c - '0';
    }

    bool same = true;
    bool seq = true;
    for(int i = 0; i < 3; i++){
        if(a[i] != a[i + 1]) same = false;
        if((a[i] + 1) % 10 != a[i + 1]) seq = false;
    }
    cout << (same || seq ? "Weak" : "Strong");
    return 0;
}

C - Min Difference (*246)

접기/펼치기

문제 설명
수열 2개가 주어진다. $N$개 양수로 이루어진 $A = (A_1, A_2, ..., A_N)$과 $M$개 양수로 이루어진 $B = (B_1, B_2, ..., B_M)$

$A$의 원소와 $B$의 원소사이의 최소 차이를 구하라. 즉 $|A_i - B_j|$의 최솟값을 구하는 것이다.

문제 해설
이번대회에서 복병이 사실 이 문제였다. 처음 이 문제를 만났을 때, 그냥 각각에서 나올 수 있는 최솟값과 최댓값을 조합해서 총 4가지 경우의 수 중 최솟값을 찾으면 되지 않을까? 라는 생각을 했다. 그런데 계속 틀려서 결국 6번을 뇌절하고 D번 문제를 풀었는데, 10분만에 바로 풀어서 다시 이 문제를 잡았다. 결국 시간제한을 줄이는 것이 목표기 때문에 lower_bound로 풀었는데, 이 풀이도 나쁘지 않았지만 더 쉬운 풀이가 있었기에 소개한다.

먼저 이러한 문제를 만나면 정렬을 하고 본다. 왜냐하면 최소 차이를 찾는 것이 문제이기 때문에 원소의 순서는 전혀 문제를 푸는데 영향을 주지 않기 때문이다. 두 배열을 오름차순으로 정렬한 다음에 두 배열에 맨 처음 원소끼리 차이를 구한다음 이 두 원소를 자세히 살펴보자. $A > B$이면 $A$에 있는 배열의 다음 원소를 선택하면 우리는 오름차순으로 정렬했기 때문에 반드시 차이가 커진다. 따라서 $B$에 있는 배열의 원소를 다음 원소로 선택해야 차이가 줄어들 가능성이 있다. 반대인 경우는 $B$가 아니라 $A$에 있는 다음 원소를 비교하면 된다.

이런식으로 문제를 풀면 시간복잡도가 최대 $O(N + M)$이므로 시간제한 안에 풀 수 있다.

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    int a[n], b[m];
    for(auto& x : a) cin >> x;
    for(auto& x : b) cin >> x;
    sort(a, a + n);
    sort(b, b + m);
    int ans = 1e9;
    int x = 0, y = 0;
    while(x < n && y < m){
        ans = min(ans, abs(a[x] - b[y]));
        if(a[x] < b[y]) x++;
        else y++;
    }
    cout << ans;
    return 0;
}

D - Querying Multiset (*775)

접기/펼치기

문제 설명
수지는 아무것도 써있지 않은 많은 공과 가방 1개를 가지고 있다. 초기에 가방은 비어있다. 수지는 연산을 $Q$번 시행할 것이고 각각은 다음 3가지 종류중 한가지이다.

• Type 1: 빈 공에 정수 $X_i$를 써넣고 가방에 넣는다.
• Type 2: 가방에 있는 모든 공에 대해서 적혀있는 숫자를 적혀있는 숫자 + $X_i$로 바꾼다.
• Type 3: 가방에 있는 공 중에서 가장 작은 숫자를 가진 공을 꺼낸다. (만약 그러한 공이 많이 있다면 아무거나 꺼낸다.) 그리고 공에 적혀있는 정수를 기록하고 버린다.

$1 \le i \le Q$ 에 대해서 $i$번째 연산의 타입 $P_i$와 만약 연산이 $Type 1$ 혹은 $Type 2$인 경우 $X_i$가 주어진다. 만약 $Type 3$이 주어지면 기록한 정수를 출력한다.

문제 해설
저번에 풀었던 문제와 같이 우선순위 큐 문제이다. 최근에 우선순위 큐를 많이 사용하는 것 같다는 느낌이 든다. 일단 내가 우선순위 큐를 사용해야겠다고 생각한 결정적인 이유는 Type 3에서 가방에서 가장 작은 숫자를 항상 꺼내야 한다는 점이었다. 숫자의 순서가 자료구조에서 숫자를 꺼내도 유지되는 자료구조는 우선순위 큐 밖에 없기 때문이었다.

그러면 1번 연산은 쉽다. 그런데 2번 연산은 어떻게 구현해야 할까? 2번 연산이 들어올 때 마다 큐에있는 모든 원소를 순회하면서 $X_i$를 더해야한다는 것은 무조건 말이 안된다. 시간이 너무 오래 걸린다.

이렇게 하면 어떨까? 가방 안에 있는 공은 그대로 두고 더해야 하는 숫자를 관리하는 변수 $num$을 만드는 것이다. 만약 모든 원소에 $5$를 더해야 한다면 num = 5이고 공을 꺼낼 때, 원래 값에 num을 더한 갑을 출력하면 될 것이다. 만약 2번 타입의 연산이 계속 된다면 num은 그 값만큼 누적될 것이다.

이렇게 구현한다면 1번 타입 연산도 조금 수정해야 한다. 왜냐하면 이미 가방에는 모든 원소에 5를 더해야 하는 상황인데 새로 10이라는 숫자를 적힌 공을 그냥 넣는다면 이상한 답이 출력되기 때문이다. 10은 원래 가방안에 있던 원소가 아니기 때문에 5를 더해서 출력하면 안된다. 따라서 가방에 공을 넣을 때, 원래 숫자에 num을 뺀 값을 넣는다면 문제를 해결할 수 있다. 만약 처음에 공을 계속 넣는다면 num = 0이기 때문에 아무 영향이 없다. 위에 상황이라면 10대신 5를 넣고 공을 뺄때는 5를 더해서 빼면 원래 상태가 유지된다.

c++에서 제공하는 우선순위 큐는 max heap이기 때문에 min heap을 사용하려면 코드를 수정해줘야 한다는 점을 유의하자.

정답 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int q; cin >> q;
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    ll acc = 0;
    while(q--){
        int num; cin >> num;
        if(num == 3){
            cout << pq.top() + acc << "\n";
            pq.pop();
        }else{
            ll n; cin >> n;
            if(num == 1) pq.push(n - acc);
            else acc += n;
        }
    }
    return 0;
}