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

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

진짜 아쉬웠던 대회, 내 수준은 엣코더를 6번째 하면서 D번까지 풀면 실력이 오른거고 D번을 못풀면 실력이 아직 재자리라고 느끼는데 이번에는 접근 방법은 다 생각했는데 구현 방식을 몰라서 못풀었다. 이런 작동을 하는 효율적인 알고리즘이 무엇일까? 라는 생각의 답을 찾기 위해서는 다양한 variation의 문제를 풀면서 경험을 쌓는 수밖에 없다.
이번 대회를 참여하면서 배운 것은

1. Disjoint-Set(분리집합)의 find함수의 쓰임새

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

A - Maxi-Buying (*5)

접기/펼치기

문제 설명
Atcoder 공화국에서는 소비세가 8%이다.
이 나라의 에너지 음료 상점은 에너지 음료를 세금을 제외하고 $N$원에 판다.
세금을 포함하면 가격은 $[1.08\times N]$ 원이 된다. 이때 $[x]$는 $x$보다 크지 않은 정수 중에서 가장 큰 수를 의미한다.
만약 세금을 포함한 가격이 $206$원보다 작으면 "Yay!"를 출력하고, 가격이 같다면 "so-so$를 출력하고 가격이 크다면 ":("를 출력한다.

제약

• $0\le N\le 300$
• 모든 입력은 정수이다.

문제 해설
$n\times 1.06$을 한 값을 int에 담으면 되는 문제이다. 주의해야 할점은 int * double은 double로 자동 type casting이 되기 때문에 cout을 하면 실수로 출력된다는 것이다.

정답 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    int res = n * 1.08;
    cout << (res < 206 ? "Yay!" : (res > 206 ? ":(" : "so-so"));
    return 0;
}

B - Savings (*14)

접기/펼치기

문제 설명
진수는 빈 돼지저금통을 가지고 있다.
$i$번째 아침에 진수는 저금통에 $i$원을 넣는다. 즉 $1$번째날에는 1원을 넣고, $2$번째 날에는 2원을 넣는다.
각 밤마다 진수는 돈이 얼마나 있는지 확인한다.
각 날 밤에 진수가 돼지저금통을 확인했을 때 $N$원이거나 $N$원보다 크게 되는 날은 언제일까?

제약

• $1\le N\le {10}^9$
• 모든 입력은 정수로 이루어져 있다.

문제 해설
$1$부터 $n$까지 반복문을 돌려서 $res>=n$인 순간의 답을 구하거나, 등차수열이므로 $(i+1)\times i/2$ 의 값이 $n$보다 큰 $i$를 구하면 된다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    int ans = 0, res = 0;
    for(int i = 1; res < n; i++){
        res += i;
        ans++;
    }
    cout << ans;
    return 0;
}

C - Swappable (*171)

접기/펼치기

문제 설명
$N$개 정수로 이루어진 배열 $A=(A_1,A_2,...,A_N)$이 주어진다. 다음 모든 조건을 만족하는 순서쌍 $(i,j)$의 개수를 구하자.

• $1\le i<j\le N$
• $A_i\ne A_j$

제약

• $2\le N\le 3\times {10}^5$
• $1\le A_i\le {10}^9$
• 모든 값은 정수로 주어진다.

문제 해설
이전에 풀었던 ABC200-C와 아주 유사한 문제이다. 결국 $i<j$ 이기 때문에 전체에서 두 수를 선택만 하면 자동으로 순서가 보장되는 조합을 이용해서 문제를 풀면 된다.

전체 조합인 $N\mathrm{C}2$ 에서 각 숫자가 출현한 횟수에서 2를 선택하는 조합을 취한 모든 값을 빼면 된다. 만약 $2$가 3번 나왔고, $10000$이 10번 나왔다면 전체에서 - $3\mathrm{C}2$ - $10\mathrm{C}2$ 을 하면 된다.

이때 $A_i$의 값은 ${10}^9$ 까지이므로 배열의 한도를 초과하니 연관 자료형인 std::map을 사용한다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    long long n; cin >> n;
    int arr[n];
    map<int, long long> mp;
    long long res = n * (n - 1) / 2;
    for(int i = 0; i < n; i++){
        int num; cin >> num;
        mp[num]++;
    }

    for(auto x : mp) res -= (x.second * (x.second - 1) / 2LL);
    cout << res;
    return 0;
}

D - KAIBUNsyo (*879)

접기/펼치기

문제 설명
$N$개 정수로 이루어진 배열 $A=(A_1,A_2,...,A_N)$이 주어진다. 우리는 아래에 있는 연산을 한번이상 수행하거나 수행하지 않을 수 있다. $A$를 펠린드롬으로 만들기 위해서 필요한 최소 연산의 개수는 무엇일까?

• 양수로 이루어진 순서쌍 $(x,y)$을 선택하고, $A$에 있는 모든 $x$를 $y$로 바꾼다.

우리는 $A_i=A_{N+1-i}$을 만족하는 모든 $i(1\le i\le N)$ 이 존재할 때 $A$를 펠린드롬이라고 한다.

제약

• $1\le N\le 2\times {10}^5$
• $1\le A_i\le 2\times {10}^5$
• 모든 입력은 정수로 주어진다.

문제 해설
서로 양 끝부터 비교해서 양 끝이 같으면 바꿀 필요가 없다. 그런데 양 끝이 서로 다르면 두 수 중 하나는 무조건 바꿔야하는데, 이때 $A$에 있는 모든 수를 바꿔야 하기 때문에 $A$에 mapping되는 배열을 하나 가지고 있어서 최종적으로 변하는 원소를 가리키고 있으면 좋을것 같다고 생각했다. 이때 두 수 중 어느것을 바꿔도 답에 영향은 없다.

그렇기 때문에 이 문제를 $Disjoint-Set$ 자료구조에 있는 find 함수를 이용한다. disjoint-set 자료구조의 root배열은 각 원소가 가리키고 있는 최종적인 root를 가리키게 되는데, 이것을 서로 다른 수가 만났을 때 한 수가 다른 수의 부모로 들어가게 계속 갱신해준다면, find함수의 반환값이 최종적으로 변환되는 원소를 의미한다.

즉 두 배열의 원소가 나타났을 때 각 원소의 find를 한 반환값이 최종적으로 이 수가 변하게 된 수이기 때문에 이 값을 비교해서 서로 다르면 한 원소가 다른 한 원소의 부모로 들어가게 가리키면 된다. 그러면 다음번에 같은 상황이 나오면 이때는 서로 부모가 같이 때문에 서로 같은 값을 가지게 되서 펠린드롬 조건을 충족한다. 서로 다르면 답을 1 증가시키는 것도 잊지말자.

정답 코드

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

int root[200001];
int find(int x){
    return (root[x] == x ? x : root[x] = find(root[x]));
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    for(int i = 0; i <= 200001; i++) root[i] = i;
    int arr[n];
    for(int& i : arr) cin >> i;

    int ans = 0;
    for(int i = 0; i < n / 2; i++){
        int u = find(arr[i]), v = find(arr[n - i - 1]);
        if(u == v) continue;
        ans++;
        root[u] = v;
    }
    cout << ans;
    return 0;
}