BOJ 1019 책 페이지

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

1019번: 책 페이지

풀이

문제를 풀기 위해 재귀 호출을 하면서, 문제의 구조를 일관되게 유지하는 게 핵심이다.

7683을 생각해보자.

f(7683, 1) 은 1~7683까지 일의 자리에 각 숫자가 등장하는 횟수를 세야 한다고 하자.

1~7683까지 일의 자리에 각 숫자가 몇 번씩 등장하는지 카운팅은 금방 할 수 있다. 문제는 십의 자리에서 등장 횟수를 구하기 위해 다음 재귀 호출을 할 때, 문제의 구조를 유지하기가 어렵다.

재귀 호출 구조를 간단하게 만들어야 한다.

재귀 호출 안에서 주어진 숫자 범위의 변두리에 위치한 숫자를 brute force로 처리해 구조를 일관되게 만든다.
 brute force로 1~9까지 숫자의 등장 횟수를 세고, 7680~7683까지 각 숫자가 등장하는 횟수를 센다.
남은 숫자는 10~7679까지인데  일의 자리에 각 숫자가 몇 번씩 등장하는지 카운팅을 할 수 있다. (767회)
10과 7679를 10으로 나누면 1과 767이 되는데 호출 구조가 동일해짐을 알 수 있다. 

다음 재귀호출은 f(767, 2) => "10부터 7670까지 십의 자리에 각 숫자가 등장하는 횟수"가 된다. 앞서 변두리 숫자는 전처리를 하고 나머지 부분에 대해서만 재귀 호출이 되었으므로, 10~7670사이의 구간에 일의 자리는 모두 꽉차있다. f(7683, 1)을 호출했을 때와 호출 구조도 동일하고, 최적 문제 구조에서 마지막 자리만 카운팅 하므로 0에 대한 예외처리 없이 할 수 있다. 

회고

굉장히 고생했다.

각 숫자가 일의 자리, 백의 자리, 천의 자리 ... 에 등장하는 횟수를 카운트하는 방향으로 잡았으나. 0의 처리와 각종 예외 처리가 꽤 힘들었다. 결국 이 모든 예외를 정확히 처리하는 방법을 고안해 내기도 어렵고, 그것을 구현하기는 더 어려울 거라고 생각하고 예외가 없는 방법이 있나 살펴보았다. 

재귀 호출을 이용하여 구현을 하는 것이 확실한데, 그 최적 구조가 너무 복잡해서 어려운 경우였다. 이런 경우 적절한 전처리나 후처리를 해서 문제를 재귀 호출에 용이한 구조로 제한을 하는 방법을 생각해 봐야겠다.