Boj 1019 c++ 책페이지

내 생애 첫 플레 문제.

도전해보는 마음으로 코드를 구상했는데 생각보다 알고리즘 이론에 비해 수학적인 사고력이 더 필요해서 재미있게 풀었다. 전형적인 규칙찾기 문제라고 부를 만 했다.

 

우선은 코드를 짜기 전에 어떤 식으로 횟수를 계산해봐야 할지 고민해봤다.

태그는 수학과 구현 뿐이였기에, 내가 직접 구현해야 겠다는 생각을 했다.

 

문제는 간단했다. 숫자 N(1<=N<=1,000,000,000)이 주어지면 N페이지의 책에서 각각의 페이지에 0~9까지의 숫자가 총 몇번 쓰였는지 구하는 것이였다. 

 

우선 무식하게 각자리 숫자의 등장 횟수를 구하는 방식은 무조건 아니라고 생각했다. 만약 이런식으로 부르트포스 알고리즘과 유사하게 하나하나 구한다면 반드시 시간제한에 걸리기 때문이다.

 

때문에, 우선 노트북을 덮고 종이에 임의의 수, (ex: 49, 348)의 각 자리 숫자의 등장 횟수를 직접 구해보며 규칙을 찾아내었다. 

우선은 348을 예시로 규칙을 설명하고, 이를 1~10억 까지의 수로 일반화해보겠다.

 

가장 높은 자리수의 숫자를 n이라고 정의한다.(1<=n<=9).(ex 348의 가장 높은자리수: 3)

또한 숫자의 가장 높은 자리는 10의 k승으로 약속하며 10의 k승 자리에 대한 연산을

끝마쳤을 때 n은 10의 k-1승 자리의 숫자로 바뀐다고 약속한다.(ex 348에서 1에 대한 연산을 끝마쳤을 때 n은 2로 변한다.)

또한 n을 기준으로 왼쪽에 있는 숫자를 leftnum, 오른쪽에 있는 숫자를 rightnum으로 정의한다.

(ex 348에서 n이 4일때 rightnum=8, leftnum=3) 단, 양끝 자리 수에서는 rightnum, 또는 leftnum이 존재하지 않을 수도 있다.

 

이러한 규칙을 토대로 가장 높은 자리수 부터 일의 자리수까지 순차적으로 등장 횟수를 구한다.

 

이때, 입력된 숫자 N이 한자리 수인지, 두자리 이상의 수인지 판별하고 예외처리를 해주어야 한다. 위의 규칙은 두자리 이상의 자연수에만 적용되기 때문이다. 

 

가장 높은 자리 부터 구해본다. 우선은 10^k 자리에서 1~n-1까지의 등장 횟수는 10^k번이다.

(예를 들면 348에서 백의 자리에서 1~2는 각각 10^2번, 즉 100번씩 등장했다)

그리고 n은 n의 rightnum+1만큼 등장했다.

(ex 348에서 백의자리수 3은 49번 등장했다.)

 

이제 부터는 반복 작업이다.

이번에는 10의 k-1승 부터 10의 1승까지 같은 작업으로 횟수를 구한다.

이때 0의 횟수를 오버카운팅하지 않도록 주의한다.

우선 10의 k-1자리에서는 0~9까지의 숫자가 (leftnum-1)*10^k-1만큼 등장한 후

(leftnum-1을 해주는 이유는 왼쪽 자리 숫자가 0~leftnum인 횟수를 구하되, 왼쪽숫자가 leftnum일 때와 왼쪽숫자가 0인경우를 예외처리하기 위함이다), 

1~9까지의 숫자는 10^k-1만큼 등장하고(왼쪽숫자 0일때)

0~n-1까지는 10^k-1만큼 등장하며, 마지막으로 n은 rightnum+1만큼 등장한다.(왼쪽숫자 leftnum일때)

 

이런식으로 k가 0이 될때까지 횟수를 누적해간다.

 

그리고 마지막에는 일의 자리 수가 몇번 반복되었는지 구해야 한다.

우선 0에서 9까지의 leftnum-1만큼 각각 누적해준다.(왼쪽 숫자 1~leftnum-1까지)

그리고 앞자리 수가 0인 경우는 따로 예외처리를 해준다.

그 다음 leftnum과 왼쪽 숫자가 같을 때에는 1~n까지 더해준다.

 

이런 방식으로 누적해주면 책의 각자리 숫자의 횟수를 시간 제한에 맞춰 구해낼 수 있다.

#include<iostream>

using namespace std;

int f(int n) {
    int result = 1;
    for (int i = 0; i < n; i++) {
        result *= 10;
    }
    return result;
}

int main() {
    int number, rightnum, leftnum;
    long long cnt[10]={0};

    cin >> number;

    int k = -1, temp = number;

    while (temp >= 1) {
        temp = temp / 10;
        k++;
    }

    if (k == 0) {
        for (int i = 1; i <= number; i++)
            cnt[i]++;
    } else {
        int n = number / f(k);
        rightnum = number % f(k);

        if (n >= 2) {
            for (int i = 1; i <= n - 1; i++) {
                cnt[i] += f(k);
            }
        }

        cnt[n] += rightnum + 1;

        while (1) {
            k--;
            if(k<1)
                break;
            rightnum = number % f(k);
            leftnum = number / f(k + 1);
            n = (number / f(k)) % 10;

            for (int i = 0; i <= 9; i++) {
                cnt[i] += (leftnum-1) * f(k);
            }
            for(int i=1; i<=9; i++) {
                cnt[i]+=f(k);
            }

            for (int i = 0; i <= n - 1; i++) {
                cnt[i] += f(k);
            }

            cnt[n] += rightnum+1;
        }

        leftnum = number / 10;
        n = number % 10;

        for (int i = 0; i <= 9; i++) {
            cnt[i] += leftnum-1;
        }
         for(int i=1; i<=9; i++){
            cnt[i]++;
        }

        for (int i = 0; i <= n; i++) {
            cnt[i]++;
        }





    } for (int i = 0; i <= 9; i++) {
            cout << cnt[i] << " ";
        }
}