백준 알고리즘[1019] 책 페이지

문제 및 참고 사이트

https://www.acmicpc.net/problem/1019
https://mygumi.tistory.com/180
https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1019

풀이

처음 봤을 때 이 문제를 어떻게 풀어야할지 brute force 이외에는 전혀 생각나지 않았다.

이 문제를 쉽게 풀 수 있는 핵심은 문제를 작은 단위로 나누는 것이다.

핵심 아이디어는 각 자릿수를 따로 계산하자라는 것이다.

즉, 1의 자릿수, 10의 자릿수... 를 따로 따로 세서 합치는 아이디어가 이 문제를 최적화 할 수 있는 핵심이다.

정확한 문제 풀이 이해는 백준님의 자료를 참고하자.

코드

#include <iostream>
#include <math.h>

using namespace std;

int nCount[10] = { 0 };

void calc(int n, int w) {
    while (n) {
        nCount[n % 10] += pow(10, w);
        n /= 10;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int page;
    int start = 1;
    cin >> page;
    for (int i = 0;; i++) {
        while(page % 10 != 9 && start <= page) {
            calc(page, i);
            page--;
        }

        while(start % 10 != 0 && start <= page) {
            calc(start, i);
            start++;
        }

        if (start > page) break;

        for (int j = 0; j < 10; j++) {
            nCount[j] += ((int)(page / 10) - (int)(start / 10) + 1) * (int)pow(10, i);
        }
        page /= 10;
        start /= 10;
    }

    for(int i = 0; i < 10; i++) {
        cout << nCount[i] << " ";
    }
    return 0;
}

처음엔 백준님의 자료를 보고 혼자 풀어보려고 했지만 위 블로그에 정말 깔끔한 풀이가 있어서 코드를 갈아엎고 블로그에 적혀있는 코드를 참고하여 알고리즘을 짰다. 코드를 짤때 너무 돌아간 것 같다. 깔끔한 코드를 짜려고 더 고민해야할 것 같다. 문제를 나누고, 따로 해결하고 합치기.