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

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

D번 문제까지 풀어서 1000점 가량 퍼포먼스가 나와서 가상 레이팅 점수가 올랐다. 정말 뿌듯했다. DP문제를 시간내에 해결했다는 점이 정말 고무적인 성과라고 생각한다. 이제 ATcoder 1400점 갈수 있을까?

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

A - Exact Price (*6)

접기/펼치기

문제 설명
천호의 지갑에는 1개 이상의 $100$원 동전뿐이 있고, 나머지 종류의 동전은 없다.
이 지갑을 사용해서 정확히 $X$원을 지불할 수 있을까?

문제 해설
나머지 연산을 사용합시다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int x; cin >> x;
    cout << (x == 0 ? "No" : (x % 100 ? "No" : "Yes"));
    return 0;
}

B - String Shifting (*86)

접기/펼치기

문제 설명
문자열이 있을때, 왼쪽 이동 은 맨 처음 문자를 문자열 맨 끝으로 이동하는 것이고, 오른쪽 이동 은 맨 마지막 문자를 문자열 맨 앞으로 이동하는 것이다.

영어 소문자로 이루어진 문자열 $S$가 주어질때, 0번 혹은 그 이상의 왼쪽, 오른쪽 이동 연산을 통해서 얻어진 문자열들 중에서 사전순으로 제일 작은 문자열과 제일 큰 문자열을 출력하라.

문제 해설
$S$의 제한이 $1000$이므로 그냥 모든 경우를 탐색하면된다. 한 문자열을 기준으로 왼쪽, 혹은 오른쪽 이동을 계속 수행해서 나온 문자열을 모두 담아 정렬하면 끝.

정답 코드

#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;
    vector<string> v;
    int n = s.size();
    for(int i = 0; i < n; i++){
        v.push_back(s.substr(i, n - i) + s.substr(0, i));
    }
    sort(v.begin(), v.end());
    cout << v[0] << "\n" << v[n - 1];
    return 0;
}

C - Doukasen (*354)

접기/펼치기

문제 설명
$N$개의 퓨즈가 일렬로 연결되어 있다. $i$번째 퓨즈는 왼쪽에서 $A_i$cm만큼 길이를 가지고 있고, 1초에 $B_i$cm 일정한 속도로 탄다.

이 물체가 왼쪽끝과 오른쪽 끝에서 동시에 태울때, 두 불꽃이 서로 만나는 지점의 길이를 왼쪽 끝에서부터 계산하라.

문제 해설
이 문제의 핵심은 거리와 속력 그리고 시간 사이의 관계를 이해하는 것과 동시에 태운다는 상황을 이해하는 것이다. 시간은 거리 / 속력이기 때문에 한 도화선이 전부 탈때까지 걸리는 시간은 $\frac{A_i}{B_i}$ 이다. 그리고 전체 타는 시간은 모든 경우를 더하면 되고, 왼쪽끝과 오른쪽 끝에서 동시에 태웠기 때문에 두 불꽃은 전체 걸리는 시간의 절반만큼인 지점에서 만난다. 그리고 그 시간에서의 위치를 찾으면 된다.

$N$이 $100000$ 까지이므로 완전탐색으로 맨 앞에서부터 계산하면 된다.
전체시간의 절반을 $t$라고 할때, 한 도화선이 타는데 걸리는 시간보다 $t$가 크다면 이 지점에서는 두 불꽃이 만나지 않았다는 것이기 때문에 그만큼의 길이를 더해주고, 타는데 걸리는 시간을 $t$에서 빼준다.

이렇게 반복문을 수행할때, 한 도화선이 타는데 걸리는 시간이 $t$보다 작은 순간이 있고, 바로 그 지점의 길이를 최종적으로 구해서 더하면 우리가 원하는 답이 나온다.

정답 코드

#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;
    double a[n], b[n], t = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i] >> b[i];
        t += (a[i] / b[i]);
    }
    t /= 2;
    double ans = 0;
    for(int i = 0; i < n; i++){
        ans += min(a[i], t * b[i]);
        t -= min(a[i] / b[i], t);
    }
    cout << fixed << setprecision(15);
    cout << ans;
    return 0;
}

D - Restricted Permutation (*1069)

접기/펼치기

문제 설명
$(1, 2, ..., N)$으로 이루어진 다음 조건을 만족하는 순열 $P$ 중에서 사전순으로 가장 작은 순열을 출력하라.

• $i = 1, ..., M$에 대해서 $A_i$는 $P$에서 $B_i$보다 먼저 나와야 한다.

만약 그러한 $P$가 없다면 $-1$을 출력하라.

문제 해설
문제 보자마자 위상정렬을 사용하는 문제라는 것을 알았다. 그리고 위상정렬을 set을 사용해서 하다가 피를 봤다. 그리고 다음에는 반드시 vector를 사용해서 인접 리스트를 구현해야 한다는 사실도 깨달았다.

위상정렬 구현하는 방법이 가물가물해서 인터넷을 보고 구현했지만 처음 구현한것 치고 잘했다. 결국 위상정렬은 indegree를 관리해야 하는데, 노드의 indegree란 DAC일때, 화살표를 받는 개수를 구하면 되는 것이다. 그리고 indegree가 없는 노드들 부터 위상정렬을 시작하면 되는데, 여기서 변형을 준 점은 보통 큐를 사용해서 위상정렬을 구현하지만 이 문제에서는 사전순으로 가장 작은 순열을 구해야 하기 때문에 우선순위큐를 사용해서 나중에 들어와도 정렬이 유지되게 했다.

주의해야할 점은 c++에서 우선순위 큐의 기본값은 max heap이기 때문에 min heap을 사용하려면 greater 함수를 추가해야 한다는 점이다. 그리고 이거 빼고는 나머지 구현방식은 그냥 위상정렬과 같다.

정답 코드

#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;
    vector<vector<int>> g(n + 1);
    vector<int> indeg(n + 1);
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        indeg[b]++;
    }

    priority_queue<int, vector<int>, greater<int>> pq;
    vector<int> ans;
    for(int i = 1; i <= n; i++) if(!indeg[i]) pq.push(i);

    while(pq.size()){
        int top = pq.top();
        pq.pop();
        ans.push_back(top);
        for(auto x : g[top]){
            if(--indeg[x] == 0) pq.push(x);
        }
    }

    if(ans.size() != n){
        cout << -1;
        return 0;
    }

    for(auto x : ans) cout << x << " ";
    return 0;
}