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

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

역대 최악의 퍼포먼스가 나올거 같지만 그냥 묵묵히 나는 문제를 푼다. 모르면 모르는데로, 알면 아는데로 문제를 계속 풀자. 내 머리를 조각하는 느낌으로

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

A - Seismic magnitude scales (*10)

접기/펼치기

문제 설명
지진의 진도는 지진에 의해 발생한 에너지크기의 로그를 씌운 값이다.
진도가 1 상승할때마다 에너지의 양은 32를 곱한 만큼 상승한다.
진도 $A$는 $B$보다 얼마나 큰 에너지를 가지고 있을까?

문제 해설
솔직히 문제는 이해 안됐지만 예시를 보면 간단히 이해할 수 있는 문제이다. 로그 스케일을 사용하기 때문에 로그의 성질을 사용하는 것이 이 문제의 해답.

정답 코드

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

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

B - typo (*58)

접기/펼치기

문제 설명
두 문자열 $S$와 $T$가 주어진다. 다음 연산을 최대 한번 수행했을때 $S$와 $T$를 같게 만들 수 있는지 확인하라.

• $S$의 두 인접한 문자를 선택하고 바꾼다.
  위 연산을 수행하지 않아도 상관 없다.

문제 해설
일단 연산을 0번 수행 했을 경우를 확인하기 위해서 $S == T$인 경우를 확인하고, $S$를 반복해서 확인하면서 인접 index를 교환했을 때 그 문자열이 $T$와 같은지 확인한다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string s, t; cin >> s >> t;
    if(s == t){
        cout << "Yes";
        return 0;
    }

    for(int i = 0; i < s.size() - 1; i++){
        string tmp = s;
        swap(tmp[i], tmp[i + 1]);
        if(tmp == t){
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
    return 0;
}

C - Select Mul (*379)

접기/펼치기

문제 설명
정수 $N$이 주어진다. 정수 $N$의 각 자릿수를 순열로 만든 다음 두 그룹으로 묶어서 두 양의 정수로 나눈다. 두 양의 정수로 나뉠때 맨 앞에 $0$이 온 경우는 제외한다. 추가로 나눈 양의 정수는 $0$보다 커야한다.

두 양의 정수의 곱중 가장 큰 값은 무엇일까?

문제 해설
사실 이 문제를 처음 봤을때는 정수를 문자열로 간주하고 내림차순으로 정렬하고 맨 앞부터 차례로 그리디하게 $a$, $b$ 처럼 순차적으로 분배하면 될줄 알았지만 그렇게 하니까 계속 틀려서 결국 이 문제를 못풀었다.

이 문제의 해답은 그냥 완전탐색이였다. 알고리즘 문제 중에서 next_permutation쓰는 문제를 별로 안좋아하는데, 이 문제가 저 함수를 쓰면 바로 풀리는 문제라서 너무 허탈했다. 일단 최대 자릿수인 $9!$이 시간 널널하기 때문에 저 완전탐색이 사용가능하다.

또한 항상 주어진 순열을 절반으로 나누는 경우가 최대이기 때문에 그냥 모든 경우의 수를 확인하면 된다.

정답 코드

#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;
    sort(s.begin(), s.end());
    int ans = 0, n = s.size() / 2;
    do{
        string a = s.substr(0, n), b = s.substr(n);
        ans = max(ans, stoi(a) * stoi(b));
    }while(next_permutation(s.begin(), s.end()));
    cout << ans;
    return 0;
}

D - Online games (*832)

접기/펼치기

문제 설명
유저 $N$명이 등록한 온라인 게임이 있다.
오늘은 게임이 출시한지 $10^{100}$번째 되는 날이다. 개발자는 유저의 로그인 기록을 조사했다. 개발자는 $i$번째 유저가 $A_i$날 부터 연속해서 $B_i$날 동안 로그인 했다는 것을 확인했다. 그리고 첫번째 날은 이 게임이 출시한 날이고, $i$번째 유저는 저 날 아니면 로그인을 안했다. 다시 말하면 $i$번째 유저는 $A_i, A_i + 1, ..., A_i + B_i - 1$ 날동안만 접속했다.

$1 \le k \le N$을 만족하는 모든 $k$에 대해서 정확히 $k$명이 로그인 한 날의 수를 구하라.

문제 해설
솔직히 그냥 몰랐었다. 이런 문제는 어떻게 풀어야 할까? 답은 그냥 푸는 것이다. 비슷한 유형을 계속 풀어서 익숙해져야 한다. 뭐 특출난 자료구조도 아니고, 그리디 유형의 문제라고 할 수 가 있는데, 이렇게 문제가 나오는 경우가 많기 때문에 내가 그리디 유형의 문제를 잘 못푸는 것 같다.

문제 접근은 여기서 부터 출발한다. 모든 사람의 로그인을 시작한 날짜와, 로그아웃을 한 날짜를 모두 한 배열에 담아서 정렬을 한다. 물론 이 배열에 있는 날짜 원소에는 로그인을 시작했는지, 로그아웃을 했는지는 표시 해야한다. 그러면 $i$번째 날이 있을 때, $i+1$날에서 $i$번째 날 사이에는 로그인한 사람의 수가 변하지 않는다. 즉 일정하다는 것이다.

그러면 이제 그냥 $i$번째 날에 사람이 몇명있는지 단순히 계산만 하면 되는 문제가 되는 것이다. $0$명으로 시작했다가 어떤 사람이 로그인 한 날이 있으면 명수를 올리고 그 다음날까지 일수를 계산한 다음에 이 날에는 사람이 일정하기 때문에 그 날 만큼 현재 로그인한 사람을 index로 한 배열의 값을 증가한다. 마찬가지로 어떤 사람이 로그아웃한 날이 있으면 명수를 줄이고 위의 과정을 반복하면 쉽게 풀 수 있는 문제다.

솔직히 그냥 그리디 + 애드혹 문제였던 것 같다. 답을 보면 쉬운데, 발상이 너무 어렵다. ㅠㅠ

정답 코드

#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<pair<int, int>> v;
    for(int i = 0; i < n; i++){
        int a, b; cin >> a >> b;
        v.push_back({a, 1});
        v.push_back({a + b, -1});
    }
    sort(v.begin(), v.end());

    int ans[n + 1] = {0, }, cnt = 0;
    for(int i = 0; i < v.size() - 1; i++){
        cnt += v[i].second;
        ans[cnt] += (v[i + 1].first - v[i].first);
    }
    for(int i = 1; i <= n; i++) cout << ans[i] << " ";
    return 0;
}