백준/1019번/책 페이지/골드1

January 24, 2024

카테고리: CodingTest

Problem Link: https://www.acmicpc.net/problem/1019

문제 설명

Site: Baekjoon
Number: 1019
Category: Mathematics
Rank: Gold 1

1부터 N까지 숫자를 세며 0~9까지 숫자가 몇번씩 나오는지 구하는 문제입니다.

문제 풀이

처음에 N까지 for문을 진행하며 세려 했지만 N의 한계치가 10억이기 때문에 시간초과가 발생할 것 같아 수학적 패턴을 찾아 해결하였습니다.

해결한 방법은 다음과 같습니다.

주어진 숫자가 1의 자릿수라면 해당 숫자까지 나오는 숫자들을 저장하여 출력하고 종료합니다.

그 이상의 자릿수라면 다음과 같은 과정을 통해 해결합니다.

n자릿수를 만드는데 숫자가 등장하는 횟수를 따로 배열에 저장합니다.

n자릿수 만들 때 숫자가 등장하는 횟수

등장하는 횟수는 10의 n-1승 + n-1자릿수 * 10입니다.

ex) 3자릿수 1~99까지 가는데 등장하는 횟수는 각 숫자 별 20번씩 등장하며, 4자릿수를 만들 때 1~999까지 등장횟수는 숫자마다 300번씩 등장합니다.
n자릿수를 만드는데 0이 등장하는 횟수도 따로 배열에 저장합니다.

다른 숫자와 달리 0은 첫 숫자로 나올 수 없으므로 등장하는 횟수는 (0의 n-1자릿수) + (1~9숫자의 n-1자릿수 * 9)입니다.
주어진 숫자가 n자릿수일때, n자릿수를 만들때 필요한 숫자의 양을 각 숫자값에 더합니다.
1번째 자리부터 각 자릿수마다 횟수를 앞 자릿수에 곱하고, 0~n까지의 횟수를 구하여 정답 배열에 더합니다.
마지막 자리는 n자릿수를 만들 때 필요한 숫자의 양을 마지막 자릿수 - 1만큼 모든 수의 정답 배열에 더합니다.

예시

51247의 경우

#include <iostream>

using namespace std;

long long cnt[11];
long long zero[11];
long long digits[11];
long long answer[10];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cnt[1] = 1;
    zero[1] = 0;

    // i자릿수 만들때 들어가는 숫자의 양
    for(long long i = 2; i < 11; i++)
    {
        cnt[i] = pow(10, i - 1) + cnt[i - 1] * 10;
        zero[i] = zero[i - 1] + (cnt[i-1] * 9);
    }

    long long N, tmp;
    cin >> N;

    tmp = N;

    // 자릿 수
    int dig = 1;

    // 자릿 수 계산 및 각 자릿 수 저장
    while(tmp > 0)
    {
        digits[dig] = tmp % 10;
        tmp /= 10;
        dig++;
    }

    dig--;

    //자릿수 - 1만큼 숫자 만들 때 드는 양
    answer[0] = zero[dig - 1];
    for(int i = 1; i < 10; i++)
        answer[i] = cnt[dig - 1];

    // 1의 자릿수에 따른 앞 자릿수 횟수 추가
    for(int i = 2; i <= dig; i++)
        answer[digits[i]] += digits[1] + 1;

    // 1의 자릿수에 따른 추가
    for (int i = 1; i <= digits[1]; i++)
        answer[i]++;

    if (dig != 1)
    {
        for (int i = digits[dig] - 1; i > 0; i--)
        {
            answer[i] += pow(10, dig - 1);
            for (int j = 0; j < 10; j++)
                answer[j] += cnt[dig - 1];
        }
        answer[0]++;
    }

    //2자릿수 부터
    for(int i = 2; i < dig; i++)
    {
        int num = digits[i];

        for(int j = i + 1; j <= dig; j++)
        {
            answer[digits[j]] += num * pow(10, i - 1);
        }

        for(int j = num - 1; j >= 0; j--)
        {
            answer[j] += pow(10, i - 1);

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

    for (int i = 0; i < 10; i++)
        cout << answer[i] << " ";

    return 0;
}

평생하는 개발 공부

문제 설명

문제 풀이