1019번: 책 페이지

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

1019번: 책 페이지

입력의 범위가 1부터 10^9이므로, 1부터 N까지 모든 수를 하나하나 세어가면서 진행하면 시간 초과가 발생하게 된다. 따라서 이 문제는 N을 (10 ^ k)의 자리에 대해 해당 자리의 수 mid와 mid의 좌우에 있는 두 수 left와 right를 이용해서 해답을 찾아내야 한다. 

 

해답만 먼저 말하자면, (10 ^ k)의 자리에 임의의 수 i가 올 수 있는 경우의 수는 다음과 같다.

• i <  mid => (left + 1 - (i == 0)) * log
• i == mid => (left - (i == 0)) * log + (right + 1)
• i >  mid => (left - (i == 0)) * log

어째서 이러한지는 수 385을 통해 알아가보도록 하자.

 

우선 385의 1의 자리에 대해서 보자. 1부터 385까지 중 1의 자리에 0, 1, 3, 5, 8, 9가 올 수 있는 경우를 보면

• 0 : 10, 20, 30, 40, ... , 370, 380
• 1 : 1, 11, 21, 31, ... , 371, 381
• 3 : 3, 13, 23, 33, ... , 373, 383
• 5 : 5, 15, 25, 35, ... , 375, 385
• 8 : 8, 18, 28, 38, ... , 378
• 9 : 9, 19, 29, 39, ... , 379

보다시피 0의 경우는 38개, 1, 3과 5는 38 + 1개, 8과 9의 경우는 38개를 가지는 것을 알 수 있다. 이 때 left는 38, right는 0이다.

 

또 385의 10의 자리에 대해서 보자. 1부터 385까지 중 10의 자리에 0, 1, 3, 5, 8, 9가 올 수 있는 경우를 보면

• 0 : 100, 101, 102, ... , 109, 200, 201, ... , 209, 301, ... , 309
• 1 : 10, 11, 12, ... , 19, 110, 111, .. , 119, 210, ... , 219, 310, ... , 319
• 3 : 30, 31, 32, ... , 39, 130, 131, .. , 139, 230, ... , 239, 330, ... , 339
• 5 : 50, 51, 52, ... , 59, 150, 151, .. , 159, 250, ... , 259, 350, ... , 359
• 8 : 80, 81, 82, ... , 89, 180, 181, .. , 189, 280, ... , 289, 380, ... , 385
• 9 : 90, 91, 92, ... , 99, 190, 191, .. , 199, 290, ... , 299

보다시피 0의 경우는 3 * 10개, 1, 3과 5는(3 + 1) * 10개, 8은 3 * 10 + (5 + 1)개, 9는 3 * 10개를 가지는 것을 알 수 있다. 이 떄 left는 3, right는 5이다.

 

마지막으로 385의 100의 자리에 대해서 보자. 1부터 385까지 중 100의 자리에 0, 1, 3, 5, 8, 9가 올 수 있는 경우를 보면

• 1 : 100, 101, ... , 199
• 3 : 300, 301, ... , 385

보다시피 0의 경우는 없고, 1의 경우는 100개, 3의 경우는 85개, 나머지의 경우는 0개임을 알 수 있다. 이 때 left는 0, right는 85이다.

 

위의 각 수의 개수를 보면, (10 ^ k)의 자리에 i가 올 수 있는 경우의 수는 i == 0일 때, i < mid일 때, i == mid일 때, i > mid일 때의 네 가지 경우로 나뉨을 알 수 있다. 이 때 각각의 경우의 수를 따져보면

• i == 0 : 경우의 수가 left * (10 ^ k)개임을 알 수 있다.
• i < mid : 경우의 수가 (left + 1) * (10 ^ k)개임을 알 수 있다.
• i == mid : 경우의 수가 left * (10 ^ k) + right임을 알 수 있다.
• i > mid : 경우의 수가 left * (10 ^ k)임을 알 수 있다.

이 때 i == 0인 경우는 나머지 경우에서 left에 1을 뺀 경우와 같으므로,

1부터 N까지의 모든 수에서 (10 ^ k)의 자리에 i가 나오는 경우의 수는

• i <  mid => (left + 1 - (i == 0)) * log
• i == mid => (left - (i == 0)) * log + (right + 1)
• i >  mid => (left - (i == 0)) * log

와 같다.

#include <cstdio>

// for문 간소화
#define FOR(a, b) for (int i = a; i < b; i++)

int main() {
    // arr[digit]: 범위 안의 각 수에서 각 digit이 나오는 횟수
    // log: 수 N의 각 자리 수를 뽑아내기 위한 10^k승 변수
    // left, right: (10 ^ k)번째 자리 수의 왼쪽/오른쪽에 있는 수
    // mid: N의 (10 ^ k)번째 수
    int N, arr[10] = { 0, }, log = 1, left, right, mid;
    // 주어진 경우에 대해
    scanf("%d", &N);
    
    // N의 각 자리 수에 대해
    while (N >= log) {
        // left, right, mid 초기화
        left = N / (log * 10);
        right = N % log;
        mid = (N / log) % 10;

        // 자세한 설명은 위의 글을 참고
        FOR(0, mid) arr[i] += (left + 1 - (i == 0)) * log;
        arr[mid] += (left - (mid == 0)) * log + (right + 1);
        FOR(mid + 1, 10) arr[i] += left * log;

        // (10 ^ k)의 자리 수일 때의 계산이 끝났으므로 (10 ^ (k + 1))의 자리 수에 대해 계산
        log *= 10;
    }

	// 1부터 N까지의 모든 수에서 각 자리에 i가 나오는 경우의 수를 출력
    FOR(0, 10) printf("%d ", arr[i]);
    printf("\n");

    return 0;
}