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

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

충격적이라고 느낀 문제 set, C번하고 D번을 모두 못풀어서 짜증이 났던 문제다 도대체 나는 천장을 얼마나 두들겨야 그 고지를 넘어갈 수 있을까? 심지어 C번문제는 거의 다 접근했는데 한가지 생각을 못해서 못풀었고, D번 문제는 접근방법 조차 생각을 못해서 배울 점이 개인적으로 많았다고 느끼는 문제다.

1. bipartite graph(이분 그래프)의 정의 및 활용

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

A - Counting (*5)

접기/펼치기

문제 설명
$A$보다 작지않고 $B$보다 크지 않은 정수는 몇개일까?

문제 해설
일단 $A$부터 $B$까지 정수의 개수를 물어보는 문제이기 때문에 $B - A + 1$ 공식을 이용해서 문제를 풀면 된다. 이때 주의해야할 점은 음수가 나올 수도 있는데, 이때는 그러한 수가 없다는 뜻이기 때문에 0을 출력하면 된다. std::max()를 이용하면 쉽게 해결.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int a, b; cin >> a >> b;
    cout << max(0, b - a + 1);
    return 0;
}

B - Can you buy them all? (*13)

접기/펼치기

문제 설명
타카하시 가게에는 물건 $N$개를 판다. $i$번째 물건의 가격은 $A_i$원이다.
오늘은 할인 날이라서 $2$번째, $4$번째, 그리고 모든 짝수번째 물건의 가격은 1원 할인하고, 나머지 홀수번째 물건의 가격은 변동이 없다.
당신은 $X$원이 있는데, 정확히 물건 $N$개를 모두 살 수 있을까?

문제 해설
짝수일때 1을 뺀 값을, 홀수일 때는 그냥 값을 전부 더해서 그 값이 현재 가지고 있는 돈보다 작거나 같으면 모든 물건을 살 수 있다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, x; cin >> n >> x;
    int res = 0;
    for(int i = 1; i <= n; i++){
        int num; cin >> num;
        res += (i & 1 ? num : num - 1);
    }
    cout << (res <= x ? "Yes" : "No");
    return 0;
}

C - Not Equal (*285)

접기/펼치기

문제 설명
정수 $N$개로 이루어진 수열 $C$가 주어진다. 다음 조건을 모두 만족하는 정수 $N$개로 이루어진 수열 $A$의 개수를 찾아라.

• $1 \le A_i \le C_i (1 \le i \le N)$
• $A_i \neq A_j (1 \le i < j \le N)$

이 값은 매우 크기 때문에 값을 $(10^9 + 7)$로 나눈 값을 출력한다.

문제 해설
두번재 조건의 뜻은 수열에 있는 모든 수가 서로 달라야 한다는 뜻이기 때문에 맨 처음에 있는 원소는 그대로 두고, 두번째 부터 앞에서 쓴 개수의 원소만큼 차례로 뺀 값을 계속 곱해나가면 된다는 생각을 했는데, 거기까지만 생각하니까 답이 틀렸다. 여기서부터 무한 지옥이 시작됐다.

정렬이 되지 않은 상태에서 하니까 첫번째 조건을 만족 못하는 예외 상황이 발생했기 때문이다. 만약 배열이 $[10, 5, 2]$ 이라면 내가 처음 생각한 방법으로 하면 첫번째 수는 $10$개, 두번째 수는 앞에서 1개의 수를 썼으므로 $5 - 1$개 세번째 수는 앞에서 2개의 수를 썼으므로 $2 - 2$개 이런식으로 답을 구했기 때문에 이 수열에서는 답이 0으로 나오지만 반례가 바로 생각난다. $[9, 3, 1]$ 이런 경우가 있는데, 뇌절을 너무 많이 해서 계속 붙잡다가 못풀었다.

이 모든 사단이 일어난 원인은 모두 정렬을 하지 않았기 때문이고, 정렬을 해도 답에 영향을 주지 않는다는 것을 알아야 하는 문제였다. 오름차순하고 내가 생각한 방법대로 하면 답이 나온다.

정답 코드

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

const int mod = 1e9 + 7;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    int arr[n];
    for(auto& x : arr) cin >> x;
    sort(arr, arr + n);
    long long res = 1;
    for(int i = 0; i < n; i++){
        res *= max(0, arr[i] - i);
        res %= mod;
    }
    cout << res;
    return 0;
}

D - Collision (*686)

접기/펼치기

문제 설명
타카하시 왕국에는 도시 $N$개와 도로 $N - 1$개가 있다. 도시는 $1$부터 $N$까지 번호가 붙여져 있고 $i$ 번째 도로 $(1 \le i \le N - 1)$ 는 도시 $a_i$ 부터 도시 $b_i$방향으로 연결되어 있는 양방향 도로이다. 모든 도로는 똑같은 길이를 가지고 있다.

$Q$개의 질의가 주어지고 $i$번째 질의에서 $(1 \le i \le Q)$ 정수 $c_i$와 $d_i$가 주어진다. 다음 문제를 풀어보자.

• 타카하시는 도시 $c_i$에 있고 아오키는 도시 $d_i$에 있다. 그들은 동시에 각 도시에서 출발하고 같은 속도로 이동한다. 타카하시는 $d_i$를 향해, 아오키는 도시 $c_i$를 향해 이동한다. 그들이 도시에서 만나는지, 도로의 한 가운데에서 만나는지 결정하자. 이때 모두는 최단경로로 이동한다고 가정하고 도시를 통과하는데 드는 시간은 무시한다.

문제 해설
atcoder에서 그래프 문제가 D번에 자주 등장하는데 등장할 때 마다 항상 새로운 주제를 가지고 오는 것 같아서 좋다. 내가 그래프 문제중 못푸는 경우는 진짜 몰라서 못푸는 경우 밖에는 아직 없기 때문에 항상 배운다는 마음을 가지고 문제에 임하자.

이 문제는 이분 그래프에 대한 개념이 있어야 풀 수 있는 문제이다. 이분 그래프가 뭔지는 쉽게 찾을 수 있지만 자료구조가 트리 형식이면 반드시 이분 그래프이다. 라는 성질은 쉽게 알기 힘들다. 그래프가 트리구조가 되기 위해서는 정점이 $N$개 일때 간선이 $N - 1$개이면 반드시 트리이다. 따라서 문제 조건에 도로가 $N - 1$개 라는 것으로 이미 트리구조라는 것을 간파하면 좋다.

트리 구조면 이분 그래프를 반드시 만족한다. 따라서 모든 도시는 빨간색 혹은 파란색으로 나눠서 반드시 칠할 수 있다. 각 도시를 색깔을 칠했다면 잘 생각해보자. 두 사람이 위치한 곳이 같은 색깔로 칠해져 있다면 이 두사람은 이동할 때 마다 같은 색깔로 칠해진 도시에 도착하기 때문에 결국은 한 도시에 만나게 된다. 따라서 같은 색깔로 칠해진 곳이면 "Town"을, 다른 색깔로 칠해진 곳에 있다면 두 사람이 이동할 때 마다 서로 다른 색깔로 칠해진 도시에서 만나기 때문에 한 도시에서 절대 동시에 만날 수가 없다. 따라서 도로 중간에 만날 수 밖에 없고 "Road"를 출력한다.

정답 코드

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

const int mod = 1e9 + 7;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    vector<int> g[n + 1];
    vector<int> visit(n + 1, -1);
    for(int i = 0; i < n - 1; i++){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    queue<int> q;
    visit[1] = 0;
    q.push(1);
    while(!q.empty()){
        int front = q.front();
        q.pop();
        for(int x : g[front]){
            if(visit[x] == -1){
                visit[x] = 1 - visit[front];
                q.push(x);
            }
        }
    }

    while(m--){
        int a, b; cin >> a >> b;
        cout << (visit[a] == visit[b] ? "Town" : "Road") << "\n";
    }
    return 0;
}