책 페이지( BOJ 1019 )

문제 : https://www.acmicpc.net/problem/1019

1019번: 책 페이지

 

문제 파악하기

1 페이지부터 입력된 N 페이지까지 모든 페이지에서 등장한 숫자(0-9)의 개수를 구하는 문제입니다. N의 범위가 작다면 반복문을 활용하여 쉽게 구할 수 있지만 최대 10억까지 입력될 수 있기에 단순히 반복문으로는 구할 수 없습니다. 이 경우, N을 잘게 나눠서 문제를 해결할 수 있습니다.

 

문제 해결하기

N을 어떻게 나눌 수 있을지 생각해보는 건, 어떤 상황일 때 숫자의 개수를 구하기 쉬운지 생각하면 됩니다. 만약 N이 1234라면 어떻게 구해야 좀 더 쉽게 구할 수 있을까요? 여기서 소개하는 알고리즘은 바로 N을 각각의 자릿수마다 나눠서 생각하는 방법입니다. 1페이지부터 1234페이지는 (1~999)페이지와 (1000~1234)페이지로 나눌 수 있으며, 우리는 (1~999)페이지에 포함된 전체 숫자의 개수를 파악하는게 훨씬 편합니다. (1000~1234)페이지는 마찬가지로 (1000~1199)페이지와 (1200~1234)페이지로 나눌 수 있으며, (1000~1199)페이지는 앞자리를 제외하고 (0 ~ 199)페이지로 작게 생각할 수 있습니다. (0~199)까지 0부터 9까지의 개수를 카운트한 다음에, (0~199)개만큼 앞자리 숫자인 1에 추가해주면 좀 더 작은 범위로 생각할 수 있습니다. 이렇게 N페이지까지의 범위를 잘게 나누면 좀 더 편하게 숫자의 개수를 구할 수 있습니다.

 

그럼 범위를 나눈 다음에 어떻게 개수를 구할 수 있는지 살펴봅시다. 사실 1~9까지의 숫자 개수는 카운트 하기 편리합니다. 숫자가 배치될 수 있는 경우의 수를 따진 다음에 해당 경우마다 나올 수 있는 가짓수를 카운트하면 됩니다. 예를 들어 (1 ~ 999)페이지에서 2의 개수를 세어본다고 생각해봅시다. 그럼 2는 아래와 같이 3개의 자리에 배치될 수 있습니다.

 

[ 1 ~ 999 ]  ____ ____ ____

 

만약 2가 가장 왼쪽, 즉 100의자리에 배치되었다고 가정해봅시다. 그 때, 나올 수 있는 경우의 수는 총 몇 가지일까요? 1의 자리와 10의 자리에 각각 배치할 수 있는 숫자가 10개이기 때문에 총 100가지 방법이 있습니다. 그럼 2가 중간에 배치된다면 나올 수 있는 경우의 수는 몇 가지일까요? 마찬가지로 1의 자리와 100의 자리에 배치할 수 있는 숫자가 각각 10개씩 있기에 총 100가지 방법이 있습니다. 여기서 문득 몇 가지 의구심이 생길 수 있습니다. 첫 번째, 맨 앞자리에 0이 배치될 수 있을까요? 당연히 배치될 수 있습니다. 다만, 이 때 배치되는 0은 세지 않아야 하지만 어짜피 우리는 지금 1~9까지 숫자가 나오는 개수를 세고 있으니 상관없습니다. 두 번째, 중복으로 세어지는 숫자는 따로 처리할 필요가 없을까? 다행히도 따로 처리할 필요 없습니다. 왜냐하면 우리는 2의 전체 개수를 파악하는 것이기에 2가 여러번 나오는 숫자는 여러번 세어주면 됩니다. 다만, 우리는 맨 앞자리에 현재 숫자가 배치될 수 있는지는 확인할 필요가 있습니다. 위의 예시는 (1 ~ 999)페이지이기에 상관이 없지만 만약 (1 ~ 199)페이지까지의 숫자를 파악한다고 생각해봅시다. 그럼 맨 앞에는 0 또는 1만 배치할 수 있습니다. 이 부분만 신경쓰면 1~9까지 숫자의 개수는 쉽게 파악할 수 있습니다.

 

그럼 이번에는 조금 더 까다로운 부분인 0의 개수를 세어봅시다. 기본적으로 개수를 세는 건 이전에 우리가 살펴보았던 1~9까지의 숫자 개수를 세는 방법과 동일합니다. 다만, 0은 꼭 세어야 하는 경우와 무시해야 하는 경우를 파악해야 합니다. 만약, (1 ~ 999) 사이의 페이지에서 0의 개수를 찾는다면 우리는 001 혹은 012와 같이 생략되는 0은 무시해야 합니다. 하지만 (1000~1199)페이지에서 나오는 001 혹은 012에서의 0은 무시해서는 안 됩니다. 따라서, 만약 0을 무시해야 하는 상황이라면 중복으로 계산된 경우의 수만큼을 제외해주면 되며, 0을 세어야 하는 경우에는 맨 앞자리에 0을 배치하고 세어주면 됩니다. 자세한 소스코드를 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <vector>
#include <algorithm>
#define VMAX 10
using namespace std;
 
int N, t;
long long int f;
 
int num[VMAX];
vector< int > inp;
 
int st, ed, tmp, flag, cnt;
 
 
int pow(int val, int k) {
    if(k<0) return 0;
    
    int ret = 1;
    for(int i=1;i<=k;i++) ret *= val;
    
    return ret;
}
 
// p번째 자릿수 최댓값이 pmax
void countNum(int p, int pmin, int pmax) {
    // 1 ~ 9까지 구하기
    for(int i=1;i<VMAX;i++) {
        // p번째 자리 전까지 모두 구하기
        for(int check=1;check<p;check++) num[i] += (pmax+1)*pow(10, p-2);
        
        // p번째 자리에 배치할 수 있는지 여부 확인
        if(i <= pmax) num[i] += pow(10, p-1);
        
    }
    
    // 0은 따로 구하기
    for(int check=1;check<p;check++) num[0] += (pmax+1)*pow(10, p-2);
    
    // 맨 앞자리에 0을 배치할 수 있으면 추가로 계산하기
    if(pmax < 0) return;
    else if(pmin == 0) num[0] += pow(10, p-1);
    else {
        // 맨 앞자리에 0을 배치할 수 없으면 중복으로 계산된 0 제거
        for(int check=1;check<p;check++) {
            num[0] -= pow(10, check-1);
        }
    }
}
 
int main() {
    scanf("%d", &N);
    
    t = N; f = 1;
    while(t>0) {
        inp.push_back(t%10);
        t/=10; f*=10;
    }
 
    st = (int)inp.size()-1;
    for(int i=st;i>=0;i--) {
        tmp = 1; cnt = 0;
        
        if(i != st) countNum(i+1, 0, inp[i]-1);
        else {
            if(inp[i] == 1) countNum(i, 1, 9);
            else countNum(i+1, 1, inp[i]-1);
        }
        
        // 현재 숫자를 사용하여 만들 수 있는 나머지 경우의 수 미리 더하기
        // Ex. 29를 구할 경우, (1~19)까지 나오는 숫자의 개수(num[0:9])를 먼저 구한 다음, num[2]에 (20~29)까지 총 10번의 횟수를 더해줌.
        f /= 10;
        num[inp[i]] += (N%f+1);
    }
    
    for(int i=0;i<VMAX;i++) printf("%d ", num[i]);
    
}
/*
20
ans: 2 12 3 2 2 2 2 2 2 2
*/
 

후기

섬세하게 가짓수를 파악해야 하는 수학 문제입니다. 알고리즘만 섬세하다면 구현이 까다롭지 않은 문제입니다. 하지만 저는 처음 문제를 풀 때, 비트연산을 활용해서 그런지 무척이나 고생했던 문제입니다. 오랜만에 꼼꼼하게 알고리즘을 만들 수 있게 연습했던 문제로, 좋은 수학 관련 문제라고 생각합니다.