AtCoder Beginner Contest 200 - A부터 C까지 업솔빙

KYOCERA Programming Contest 2021（AtCoder Beginner Contest 200） A부터 C까지 업솔빙

https://codeforces.com/blog/entry/66909

3년전 글이지만 이 글을 읽고 코드포스 레이팅을 올리려면 Atcoder에 있는 문제도 푸는 것을 추천하길래 오늘부터 Atcoder에 있는 A부터 C(D)번까지 문제를 직접 풀어보고 해설까지 해볼 것이다. C번 문제혹은 D번문제까지 해설하는 기준은 내가 대회 시간에 풀려고 시도했던 문제까지 업솔빙 하고 해설을 하려고 한다.

처음으로 풀어본 Atcoder 문제는 생각보다 쉬운듯 하면서 내가 모르는 well-known 알고리즘, 정수론 문제가 초반부에 나오는 것 같다. 이번 대회를 참여하면서 배운 것은

1. 나머지 연산의 성질
2. 맨 뒤에 숫자를 추가하는 연산은 string을 붙이는 방법도 있지만 간단한 수학적 계산을 통해서 구현 할 수 있다는 점이다.

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

A - Century (*5)

접기/펼치기

문제 설명
년도를 나타내는 숫자 $N$이 주어진다. $N$년은 몇세기일까?

제약

• $1\le N\le 3000$

문제 해설
이런 유형의 문제가 나오는줄 몰라서 첫 대회 때 6분이나 해맨 문제이다. $1$ 년 부터 $100$ 년까지를 1세기, $101$ 년부터 $200$ 년까지를 2세기, 이런식으로 100년의 시기를 한 세기라고 말한다.

간단하게 100으로 나누어 떨어지면 100으로 나눈 몫을 출력하고, 나누어 떨어지지 않으면 몫에 + 1한 값을 출력한다.

정답 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    cout << (n % 100 == 0 ? n / 100 : n / 100 + 1);
    return 0;
}

B - 200th ABC-200 (*20)

접기/펼치기

문제 설명
정수 $N$이 주어진다.
다음 연산을 $K$번 반복하고 나온 최종 결과 숫자를 출력한다.

• 만약 $N$이 $200$의 배수라면 $200$ 으로 나눈다.
• 그렇지 않으면 $N$을 문자열로 보고, 맨 뒤에 $200$ 을 추가한다.
  • 예를 들어 $7$은 $7200$ 이 되고, $1234$는 $1234200$ 이 된다.

제약

• 입력으로 주어지는 값은 모두 정수이다.
• $1\le N\le {10}^5$
• $1\le K\le 20$

문제 해설
간단한 구현문제이지만 다른 사람의 코드를 보고 내가 놓친것을 깨달았다. 고수들의 코드를 보는것의 중요성이 다시한번 대두되는 순간이다.

맨 뒤에 200을 추가하는 연산을 숫자에 1000을 곱하고 200을 더하는 연산으로 바꾸면 완벽히 같은 연산이 된다. 주의해야 할 점은 뒤에 붙이는 연산을 3번 연속으로만 해도 int의 범위를 가뿐히 넘어가기 때문에 long long 자료형으로 구해야 한다는 것이다.

정답 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    long long n, k; cin >> n >> k;
    while(k--){
        if(n % 200 == 0) n /= 200;
        else n = n * 1000 + 200;
    }
    cout << n;
    return 0;
}

C - Ringo's Favorite Numbers 2 (*208)

접기/펼치기

문제 설명
사과는 숫자 $200$을 좋아한다. 우리 사과를 위해서 아래에 있는 문제를 풀어주자.
$N$개의 양의 정수로 이루어진 수열 $A$가 주어진다. 다음 조건 모두를 만족하는 정수 쌍 $(i,j)$ 의 개수를 찾아보자.

• $1\le i<j\le N$
• $A_i-A_j$ 는 $200$의 배수이다.

제약

• 입력으로 주어지는 값은 모두 정수이다.
• $2\le N\le 2\times {10}^5$
• $1\le A_i\le {10}^9$

문제 해설
이 문제를 대회에서 못풀었다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 그냥 단순하게 이중 for문을 쓰면 절대 못풀것 같아서 이분탐색 같은 것을 이리저리 요리조리 써봤지만 이렇게 푸는 것이 아니였다. 이 문제도 well-known이라는 사실을 알고, 나는 알고리즘 뉴비라는 사실을 깨달음.

이 문제는 이 식의 의미만 해석하면 바로 풀 수 있는 문제이다.

• $A_i-A_j$ 는 $200$의 배수이다.

이 식의 의미는 $A_i$ 을 $200$ 으로 나눈 나머지와 $A_j$ 을 $200$ 으로 나눈 나머지가 같은 수를 구해야 한다는 뜻이다. 왜일까? 그것은 나머지 연산의 특징을 알아야 한다.

$(A-B);modC$ = $(A;modC-B;modC);modC$ 라는 식을 만족한다. 이때 $(A+B),(A\ast B),(A-B)$ 까지 만족하고, 나눗셈은 만족하지 않는다. 그렇다면 위에 있는 조건을 식으로 나타내면 무엇일까?

• $(A_i-A_j);mod;200=0$ 이고, 이 식은 $(A_i;mod;200-A_j;mod;200);mod;200=0$ 으로 바꿀 수 있다.

이때 $n$으로 나눈 나머지는 $0$ 부터 $n-1$까지 나올 수 있기 때문에 $200$으로 나눈 나머지는 $0$ 부터 $199$ 까지 나올 수 있다.
이때 위의 식을 만족하려면 $(A_i;mod;200-A_j;mod;200)$ 이 값이 $0,200,400,...$ 이 나와야 한다.
그런데, $A_i;mod;200$의 최대값이 $199$ 이기 때문에 $200,400,...$ 이런 수는 나올 수 없다.
따라서 $(A_i;mod;200-A_j;mod;200)$ 이 식의 값이 $0$이 되어야 하고, 서로 $200$으로 나눈 나머지 값이 같아야 한다.

그렇다면 나머지가 같은 두 수를 선택하는 경우의 수를 구해야 하기 때문에 간단한 조합 공식을 이용해서 값을 전부 더하면 답이 나오게 된다.

정답 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    int cnt[200] = {};
    for(int i = 0; i < n; i++){
        int num; cin >> num;
        cnt[num % 200]++;
    }
    long long ans = 0;
    for(int i = 0; i < 200; i++){
        ans += cnt[i] * 1LL * (cnt[i] - 1) / 2LL;
    }
    cout << ans;
    return 0;
}