백준 1019번: 책 페이지 (C++)

접근

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

1019번: 책 페이지

https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1019

Baekjoon Online Judge 1019번 풀이

백준님의 풀이를 참고하여 풀었다.

풀이에서는 1~N의 범위가 아닌 A~B 범위의 숫자의 갯수를 카운트해주는 함수를 만들고 이를 자릿수마다 반복하여 문제를 해결하였는데 이해하기가 쉽지 않았다.

A와 B 범위의 숫자 갯수를 카운트할 때, 둘의 일의자리가 같아지도록 A++와 B--를 조정하면서 숫자를 각각 카운트해준다.(subcounting 함수 이용, subcounting 함수는 숫자를 10으로 나누어가며 그 나머지를 이용하여 수의 갯수를 세어준다) 둘의 일의자리가 같아지고 나면 예를 들어 155부터 355까지 일의 자리를 생각 했을 때 0 부터 9까지 각각 한번씩 나오는 과정이 일의 자리에서 (355 / 10 - 155 / 10 + 1) = 21 번 나오는 규칙성을 이용하여 0~9를 21번 더해주게 된다. 같은 방식으로 각 자리수에 대해서 계산을 반복해줌으로써 문제의 답을 구할 수 있다.

코드

#include <iostream>

using namespace std;

#define endl '\n'

int N;
long long ans[10];

void subcounting(int num, int increase) {
    while (num) {
        ans[num % 10] += increase;
        num /= 10;
    }
}

void counting(int start, int end, int digit) {
    while (start % 10 && start <= end) {
        subcounting(start, digit);
        start++;
    }
    if (end < start) return;
    while (end % 10 != 9 && start <= end) {
        subcounting(end, digit);
        end--;
    }
    long long cnt = end / 10 - start / 10 + 1;
    for (int i = 0; i < 10; i++) {
        ans[i] += cnt * digit;
    }
    counting(start / 10, end / 10, digit * 10);
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    cin >> N;

    counting(1, N, 1);

    for (int i = 0; i < 10; i++) {
        cout << ans[i] << ' ';
    }
    cout << endl;

    return 0;
}

더 생각해 볼 것?

규칙성을 찾은것 같다가도 적용이 어려워 풀지 못하고, 결국 정답의 실마리도 찾지 못한 채 답안 코드를 보게 되었다. 이해도 쉽지 않았다. 다시 한번 확인해 봐야 겠다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!