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

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

atcoder에서는 동적 계획법과 간단한 그래프 문제를 공부하고. 코드포스에서는 그리디와 구현 그리고 수학 마지막으로 이분탐색을 공부하는 방식으로 생각하자. 그런데 이번 대회의 DP는 진짜 80%는 접근 했는데 점화식에서 왼쪽 항은 맞았지만 오른쪽 항이 틀려서 아쉽게 답을 참고하고 풀었다.

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

A - Find Multiple (*14)

접기/펼치기

문제 설명
$A$와 $B$사이에서 $C$의 배수인 값을 찾아라.

만약 그런 숫자가 없다면 $-1$을 출력하라.

문제 해설
$A$와 $B$가 $1000$보다 작기 때문에 그냥 완전탐색을 해도 풀린다. 아니면 다음과 같은 방법으로 간단하게 수학적으로 풀 수 있다.
$[B / C] * C$를 하면 $B$를 넘지 않는 최대 $C$의 배수를 구할 수 있고 그 값이 $A$보다 크면 답이 존재한것이고 그렇지 않으면 답이 없는 것이니 -1을 출력한다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int a, b, c; cin >> a >> b >> c;
    int x = b / c * c;
    cout << (a <= x ? x : -1);
    return 0;
}

B - Base K (*58)

접기/펼치기

문제 설명
$K$진법인 정수 $A$와 $B$가 주어진다. 10진수로 $A \times B$를 출력하라.

문제 해설
맨 뒷자리 숫자부터 차근차근히 $k$를 곱해서 더해나가는 함수를 하나 만들고 그 함수를 $A$와 $B$에 대해서 출력하자.

맨 뒷자리 숫자를 뽑아내는 방법은 $X mod 10$이고 맨 뒷자리 숫자를 삭제하는 방법은 $X / 10$이다.

정답 코드

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

using ll = long long;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll k, a, b; cin >> k >> a >> b;
    auto f = [](ll num, ll k){
        ll sum = 0;
        ll tmp = 1;
        while(num > 0){
            sum += (num % 10) * tmp;
            num /= 10;
            tmp *= k;
        }
        return sum;
    };
    cout << f(a, k) * f(b, k);
    return 0;
}

C - Long Sequence (*119)

접기/펼치기

문제 설명
$N$개 양의 정수 배열 $A = (A_1, ..., A_N)$이 주어진다. 그리고 $B$는 $A$의 복사본 $10^{100}$개를 이어 붙인 것이다.

$B$의 각 항을 왼쪽부터 오른쪽으로 더해나갔을 때, 언제 총 합계가 $X$를 첫번째로 넘을 수 있을까?

문제 해설
먼저 주어진 $X \le 10^{18}$ 의 조건을 보면 무조건 완전탐색으로는 못 푼다는 생각을 해야한다. 그러면 어떻게 계산 과정을 단축 할 수 있을까?

이 문제의 핵심은 $A$의 복제본이 반복된다는 점이다. $A$의 원소가 $N$개라면 $B$는 $N$개의 숫자가 반복된다. 따라서 $X$를 $A$의 총합으로 나눈다면 그 몫이 바로 $N$개가 반복되는 횟수이다. 따라서 몫에 $N$을 곱하면 일단 $N$의 모든 원소를 사용했을 때 횟수가 나온다.

그리고 $X$를 $A$의 총합으로 나눈 나머지를 대상으로 $A$의 모든 원소를 차례대로 순회하면서 완전탐색으로 답을 구하면 된다.

정답 코드

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

using ll = long long;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    int a[n];
    for(auto& x : a) cin >> x;
    ll x; cin >> x;

    ll sum = accumulate(a, a + n, 0ll);
    ll cnt = x / sum * n;
    x %= sum;
    ll tmp = 0;
    for(int i = 0; i < n; i++){
        tmp += a[i];
        if(tmp > x){
            cnt += i + 1;
            break;
        }
    }
    cout << cnt;
    return 0;
}

D - FG operation (*664)

접기/펼치기

문제 설명
$0$과 $9$사이 숫자로 이루어진 $N$개 정수가 원소인 $A = (A_1, ..., A_N)$이 주어진다.

수열의 길이가 $1$이 될때까지 아래에 있는 연산 $F$와 $G$를 반복한다.

• 연산 $F$: 맨 왼쪽에 있는 두 값을 삭제한다. (이들을 각각 $x, y$라고 하자.) 그리고 왼쪽 끝에 $(x + y) % 10$을 더한다.
• 연산 $G$: 맨 왼쪽에 있는 두 값을 삭제한다. (이들을 각각 $x, y$라고 하자.) 그리고 왼쪽 끝에 $(x * y) % 10$을 더한다.

각 $K = 0, 1, ..., 9$에 대해서 다음 질문에 대답을 하자.

우리가 이 연산을 할때 생기는 $2^{N - 1}$가지 가능한 방법 중에서 연산의 마지막에 $K$가 몇번 나오는가?
답이 크기 때문에 답을 $998244353$으로 나눈 나머지 값으로 구하자.

문제 해설
그냥 딱 봐도 DP문제이다 22. 이제 DP문제라는 의심이 $N$의 범위도 작을 뿐더러 $A_i$의 범위도 $10$개밖에 안되기 때문에 드는 것 같다.

그러면 이 문제를 dp로 어떻게 풀까? 나는 dp를 다음과 같이 정의했다.

• $dp(i, j) = $ 연산을 $i$번 했을 때, 맨 왼쪽 원소가 $j$인 경우의 수

이렇게 dp를 정의하면 $i = 0$인 경우에는 연산을 안했기 때문에 주어진 배열의 맨 앞에 있는 값을 출력하면 된다. 즉 초기값은 $dp[0][a[0]]$에 1을 대입하면 된다.

그리고 그 다음에는 bottom-up 방식으로 진행하면 된다.
$i$가 1인 경우에는 $i = 0$인 경우를 확인해야 한다. $i$인 경우의 숫자 값을 $j$라고 할때 모든 $j$값을 순회하면서 $a[i + 1]$ 값과 F, G연산을 각각 수행한 값을 대상으로 DP를 수행한다. 이때 $j$ 값이 $i$번째 연산에 존재했다면 숫자가 있을 것이고, 존재하지 않으면 0이 있을 것이다. 그리고 그냥 나온 횟수를 다음 $dp[i + 1]$에 더하면 계속 답이 누적되어 답이 나온다. 이때 $998244353$으로 연산을 진행할 때 마다 나눠주는 것을 잊지 말자.

정답 코드

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

using ll = long long;
const int mod = 998244353;

ll dp[100010][10];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    int a[n];
    for(auto& x : a) cin >> x;
    dp[0][a[0]]++;

    for(int i = 0; i < n - 1; i++){
        for(int j = 0; j < 10; j++){
            int x = (a[i + 1] + j) % 10, y = (a[i + 1] * j) % 10;
            dp[i + 1][x] = (dp[i + 1][x] + dp[i][j]) % mod;
            dp[i + 1][y] = (dp[i + 1][y] + dp[i][j]) % mod;
        }
    }

    for(int i = 0; i < 10; i++) cout << dp[n - 1][i] << "\n";
    return 0;
}