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

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

D번을 내가 왜 못풀었을까? 계속 강조하지만 문제를 너무 어렵게 생각하지 않는게 좋을 것 같다. 때로는 문제에서 하라는 대로 그대로 구현하는 능력도 중요하다는 것을 잊지말길. 하라는대로만 하고 그 다음 시간초과가 나면 새로운 알고리즘을 생각해보자.

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

A - Distinct Strings (*12)

접기/펼치기

문제 설명
알파벳 소문자 3글자로만 이루어진 문자열 $S$가 주어진다. $S$를 나열할 때 얻을 수 있는 서로다른 문자열의 개수는 몇개일까?

문제 해설
모든 문자가 같으면 1, 모든 문자가 다르면 6, 그렇지 않으면 3을 출력.
안그러면 그냥 정렬하고 next_permutation을 사용하자.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string s; cin >> s;
    if(s[0] == s[1] and s[1] == s[2]) cout << 1 << "\n";
    else if(s[0] != s[1] and s[1] != s[2] and s[0] != s[2]) cout << 6 << "\n";
    else cout << 3 << "\n";
    return 0;
}

B - Star or Not (*62)

접기/펼치기

문제 설명
$N$개의 노드와 $N-1$개의 간선으로 이루어진 트리가 주어진다. 이 트리가 별인지 아닌지 판단하라.
어떤 트리가 별이 되기 위해서는 한 노드가 다른 모든 노드와 간선으로 연결되어 있는 노드가 1개라도 있으면 별이다.

문제 해설
degree판단하는 것 처럼 각 정점의 degree를 모두 계산하고 정점의 degree가 n - 1인 정점이 하나라도 있으면 true를 출력한다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<int> deg(n + 1);
    for(int i = 0; i < n - 1; i++){
        int a, b; cin >> a >> b;
        deg[a]++;
        deg[b]++;
    }

    for(int i = 1; i <= n; i++){
        if(deg[i] == n - 1){
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
    return 0;
}

C - Calendar Validator (*326)

접기/펼치기

문제 설명
${10}^{100}\times 7$ 크기의 행렬 $A$가 있다. 이 행렬의 $(i,j)$번째 칸에는 $(i-1)\times 7+j$ 의 값이 들어가 있다. $(1\le i\le {10}^{1}00,1\le j\le 7)$

$N\times M$ 크기의 행렬 $B$가 주어진다. 이 행렬이 $A$의 일부분인지 판단하라.

문제 해설
$B$의 맨 왼쪽 위에 있는 원소가 있는 행과 열이 몇번째인지 먼저 구한다. 그리고 그 값부터 시작해서 순차적으로 값을 더하면서 그 위치에 아닌 값이 존재하면 false를 출력한다. 만약 해당 행의 최대값보다 큰 값이 그 행에 있는 것도 false로 한다.

정답 코드

#include <bits/stdc++.h>
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][m];
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> a[i][j];
    int r = (a[0][0] - 1) / 7, c = a[0][0] - (r * 7 + 1);
    bool flag = true;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if((r + i) * 7 + c + j + 1 != a[i][j] or (r + i + 1) * 7 < a[i][j]) flag = false;
        }
    }
    cout << (flag ? "Yes" : "No");
    return 0;
}

D - Play Train (*778)

접기/펼치기

문제 설명
연주는 장난감 기차와 함께 기차를 연결하고 해체하는 게임을 하고 있다.
$N$개의 기차가 있으며 번호가 각각 $1,2,...,N$이 부여된다.
처음에는 모든 기차가 분리되어 있다.

$Q$개의 질의가 준비되어 있고, 질의를 주어진 순서대로 진행한다. 각 질의는 3가지 종류가 있다.

• 1 x y: 기차 $y$의 앞을 기차 $x$의 뒤에 붙인다.

  • $x\ne y$ 이며,
  • $x$의 뒤에는 아무것도 연결되어 있지 않으며,
  • $y$의 앞에는 아무것도 연결되어 있지 않다.

• 2 x y: 기차 $y$의 앞과 기차 $x$의 뒤를 분리한다.

  • $x\ne y$ 이며,
  • $x와$y$가 연결되어 있는 상태이다.

• 3 x: $x$와 연결되어 있는 기차의 맨 앞부터 뒤까지 연결되어있는 모든 기차 번호를 출력한다.

문제 해설
처음에는 뭐 링크드 리스트인지 뭔지 이거 생각해서 list자료구조 쓰려고 하다가 너무 삽질을 많이 하길래 그냥 해설을 보니까 나온대로 그대로 구현하면 끝나는 문제여서 허탈했다.

문제에서 필요한 값은 해당 기차의 앞번호와 해당 기차의 뒷 번호 기차가 무엇인지만 알면 된다. 그렇기 때문에 해당 기차의 앞 번호가 담겨있는 배열과 뒷 번호가 담겨있는 배열 두개를 만들고 각 종류의 쿼리를 진행하면 된다.

그후 3번 쿼리가 나오면 해당 기차의 맨 앞으로 이동한 후, 맨 뒤로 계속 꼬리를 물면서 값을 저장해나가면 답을 완성할 수 있다. 단순하게 쉬운 문제다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, q; cin >> n >> q;
    vector<int> front(n + 1, -1), rear(n + 1, -1);
    while(q--){
        int type, x, y; cin >> type;
        if(type == 1){
            cin >> x >> y;
            front[y] = x;
            rear[x] = y;
        }else if(type == 2){
            cin >> x >> y;
            front[y] = -1;
            rear[x] = -1;
        }else{
            cin >> x;
            while(front[x] != -1) x = front[x];
            vector<int> ans;
            while(rear[x] != -1){
                ans.push_back(x);
                x = rear[x];
            }
            ans.push_back(x);
            cout << ans.size() << " ";
            for(auto x : ans) cout << x << " ";
            cout << "\n";
        }
    }
    return 0;
}