[백준] 1019 책 페이지

문제 주소 : www.acmicpc.net/problem/1019

1019번: 책 페이지

문제 확인

 

숫자 처리 구현 문제입니다. 주의해야 할 점은 첫 시작 페이지가 1이며 n자릿수 수에 재일 앞자리 수는 0이 될 수 없습니다.

 

풀이 

 

현재 자리수의 숫자 기준으로 경우의 수를 나눌 수 있습니다. 예를 들어 1234라는 수가 있을 때 첫자리부터 경우의 수를 생각해 봅시다.

XXX0 의 경우 0000은 없는 페이지 이므로 XXX에 001~123 까지 총 123의 경우의 수가 있습니다.

XXX1 ~ XXX4 까지의 경우 XXX 자리에 000~123 까지 총 124의 경우의 수가 있습니다.

XXX5 ~ XXX9 까지의 경우 XXX자리에 000~122 까지 올 수 있으므로 총 122의 경우의 수가 있습니다.

 

다음 자리 수로 넘어가면 비슷하지만 앞에 올 수 있는 수를 고려해야 합니다.

XX0Y 의 경우 XX에서는 01 ~ 12 까지 12번, Y의 경우 0 ~ 9 까지 10번, 12 * 10 총 120의 경우의 수가 있습니다.

XX1Y ~ XX3Y 의 경우 XX : 00 ~ 12, Y : 0 ~ 9 => 13 * 10 = 130

주의해야 할 점은 XX3Y의 경우 XX가 12, 즉 123Y의 경우 뒤에 Y가 0 ~ 4 까지 밖에 올 수 없습니다. 따라서 이를 처리해 주기 위해 5 ~ 9 : 5개의 경우의 수를 빼 주어야 합니다.

XX4Y ~ XX9Y 의 경우 XX : 00 ~ 11, Y : 00 ~ 99 => 12 * 10 = 120

 

따라서 다음과 같은 식으로 바꿀 수 있습니다. i는 현재 자릿수, idx는 해당 자리의 숫자, X는 앞에 올 수 있는 경우의 수, 10^Y는 뒤에는 어떠한 수도 올 수 있으므로 Y자릿수의 모든 경우의 수를 의미합니다.

• i = 0 : (X-1) * (10^Y)
• i = 1 ~ idx-1 : X * (10^Y)
• i = idx : X * (10^Y) - (10^(Y+1) - Y)
• i = idx + 1 ~ 9 : (X-1) * (10^Y)

 

코드

#include <cstdio>
 
int main(void) {
    int n, ary[10] = { 0 };
    scanf("%d", &n);
    for (int cur = n, expr = 1; cur; expr *= 10) {
        int idx = cur % 10, next = cur / 10;
        ary[0] += next * expr;
        for (int i = 1; i <= idx; i++)
            ary[i] += (next + 1)*expr;
        ary[idx] -= expr - (n%expr) - 1;
        for (int i = idx + 1; i < 10; i++)
            ary[i] += next * expr;
 
        cur = next;
    }
    for (int i = 0; i < 10; i++)
        printf("%d ", ary[i]);
}