[BOJ] 백준 1019 - 책 페이지

문제 링크

www.acmicpc.net/problem/1019

1019번: 책 페이지

 

풀이

눈물 줄줄 흘리면서 풀었습니다 ㄹㅇ 이거 제 기준으론 골드 아닙니다..

아마 더 쉬운 방법으로 구현하거나 규칙을 찾을 수 있을듯한데 그거 생각하는 것만 해도 골드는 아닌 것 같습니다.

 

백준 9527 - 1의 개수 세기

저는 위 문제와 유사한 방법으로 풀었습니다.

차이점은 2진수가 아니라 10진수고, 0의 개수까지 세주어야 해서 사고 회로가 터져나갑니다.

어쨌든 정답을 구하는 근본 논리는 위 문제와 같습니다. 해당 글을 먼저 참고해주세요.

 

누적합 배열을 정의해봅시다.

우선 0~9까지의 개수를 저장하는 Node 타입을 만들었습니다.

Node d[i][j]: i번 자릿수(0부터 시작)의 숫자가 j일 때, 1부터 [i번 자릿수가 j인 수 중 제일 큰 수] (ex. 19, 29, 399, 89999)까지의 모든 0~9 개수의 누적합.

 

여기서 생각해볼 점이 있습니다. 1 이상의 수 중에 $i$번 자릿수가 0인 수는 존재하지 않습니다. 따라서 저는 d[i][0]을 다음과 같이 정의했습니다.

d[i][0]: d[i-1][9] + (i-1 자릿수 미만의 수 앞에 모두 0을 붙였다고 가정했을 때 그 0의 개수)

 

지금 와서 드는 생각인데 d[i][0]을 좀 애매하게 정의해서 구현이 힘들어지지 않았나 싶습니다. 이 글을 참고하시는 분들은 더 효율적으로 하실 수 있을 겁니다...

 

 

이렇게 누적합을 구해놓고 이전 문제와 같은 논리로 개수를 판별합니다.

단, 가장 큰 자릿수를 제외한 나머지 자릿수에선 그보다 작은 수의 0의 개수 또한 고려해주어야 합니다. 이를 적절한 값을 더해 해결해주도록 합시다. 그 적절한 값에 대해서는 설명할 자신이 없습니다. 그거 생각하느라 너무 힘들어서 머릿속에서 정리가 안됐네요..

 

 

정답 코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vll = vector<ll>;


struct Node {
    vll cnt;

    Node() {
        cnt.resize(10);
    }

    Node operator+(const Node &o) {
        Node tmp(*this);
        for (int i = 0; i < 10; i++) {
            tmp.cnt[i] += o.cnt[i];
        }
        return tmp;
    }

    Node &operator+=(const Node &o) {
        for (int i = 0; i < 10; i++) {
            this->cnt[i] += o.cnt[i];
        }
        return *this;
    }

    void print() {
        for (int i: cnt) cout << i << ' ';
        cout << '\n';
    }
};

Node d[10][10];
int n;

Node go(int val, int i, int num, int zero, bool first = true) {
    if (i == 0) {
        Node ret = d[0][val];
        if (!first) ret.cnt[0] += 1;
        return ret;
    }
    Node ans;
    if (int j = val / num; j > 0) {
        if (j == 1) {
            if (first) ans = d[i - 1][9];
            else ans = d[i][j - 1];
            if (!first) ans.cnt[0] += num;
        } else {
            ans = d[i][j - 1];
            if (!first) ans.cnt[0] += zero;
        }
        ans.cnt[j] += val - j * num + 1;
    } else {
        ans.cnt[0] += val + 1;
    }
    ans += go(val % num, i - 1, num / 10, zero / 10, false);
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i < 10; i++) {
        d[0][i] = d[0][i - 1];
        d[0][i].cnt[i] += 1;
    }

    for (int i = 1, c = 10, zero = 1; i < 9; i++, zero += c, c *= 10) {
        d[i][0] = d[i - 1][9];
        d[i][0].cnt[0] += zero;
        for (int j = 1; j < 10; j++) {
            if (j == 1) d[i][j] = d[i - 1][9];
            else d[i][j] = d[i][j - 1];
            d[i][j] += d[i][0];
            d[i][j].cnt[j] += c;
        }
    }


    int l = -1, num = 1, zero = 1;
    for (int i = 1; i < 1'000'000'000; i *= 10, l++, num *= 10, zero += num) {
        if (n / i == 0 || i == 1'000'000'000) break;
    }
    num /= 10;
    zero /= 10;
    if (n == 1'000'000'000) {
        l = 9;
        num = n;
    }
    go(n, l, num, zero).print();
}