[백준] 1951 활자 - 반복문, 배열 없이 수식 하나로 풀이하기

문제

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

N 이하의 자연수를 0부터 9까지 활자로 표현하려면 몇 개의 활자가 필요한지 구하여라.

입력

첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)이 주어진다.

출력

첫째 줄에 필요한 활자의 수를 1234567로 나눈 나머지를 출력한다.

풀이 #1

인터넷에 있는 다른 글들은 대부분 반복문과 배열을 활용해 해결했다. 처음에 이 방법을 생각했지만, 아래의 풀이 방법이 떠올라서 아래 풀이로 방향을 바꿨다.

풀이 #2

결론적으로 말하면, 수열의 규칙성을 추론하여 일반항을 구할 수 있다면 조건문, 반복문, 배열을 전혀 쓰지 않고 단 하나의 수식으로 풀 수 있는 순수 수학 문제이다.

규칙성 파악

먼저, 입력 N을 1부터 쭉 나열해보면서, 규칙을 파악해보자.

위 표를 보면, 출력값이 N에 대한 수열이라고 생각하면, 무언가 규칙이 보인다.

특수한 경우 (N = 10^k - 1 꼴인 경우)

우선 위 표에서 나타난 특수한 경우를 먼저 살펴보자. $N = 9999$ 일 때를 생각하면, 출력값은 $1\times9+2\times90+3\times900+4\times9000$ 와 같이 표현할 수 있다.

즉 $N=10^k-1$ 일 때 수열의 일반항은 다음과 같이 멱급수로 나타낼 수 있다. ($l$ 은 항의 개수)

$$a_N=\displaystyle\sum_{k=1}^{l}{k\times(9\times10^{k-1})}$$

이 때 항의 개수, 즉 $l$ 은 얼마여야 할까? $l$ 에 대한 규칙성도 파악해 보자.

위 표를 보면, $N=10, 100, 1000$ 일 때마다 항이 하나씩 늘어나는 것을 볼 수 있다. 즉 1~9 까지는 항이 1개, 10~99까지는 2개, 100~999까지는 3개, … 이런 식이다. 따라서 입력 $N$에 따른 $l$ 값은 다음과 같이 나타낼 수 있다.

$$l = \lfloor{log_{10}N}\rfloor$$

그 외의 경우

이번에는 $N=10^k-1$ 가 아닌 경우를 살펴보자. $N=10$일 때부터 몇 가지 나열해보면 아래와 같이 마지막 항이 1부터 점차 증가하는 것을 볼 수 있다. 이는 $N=100, 1000$ 일 때부터 나열해봐도 마찬가지이다.

$a_{10} = 1\times9+2\times1$
$a_{11} = 1\times9+2\times2$
$a_{12} = 1\times9+2\times3$
…
$a_{100} = 1\times9+2\times90+3\times1$
$a_{101} = 1\times9+2\times90+3\times2$
…

좀 더 일반화하면, $N=10^k-1$ 일 때는 사실 마지막 항에 0이 곱해진 것으로 볼 수 있다.

$a_{9}=1\times9+2\times0$
$a_{99}=1\times9+2\times90+3\times0$

따라서, 다음과 같이 표현할 수 있다.

$a_{9}=1\times9+2\times(9-9)$
$a_{10}=1\times9+2\times(10-9)$
$a_{11}=1\times9+2\times(11-9)$
…
$a_{99}=1\times9+2\times90+3\times(99-99)$
$a_{100}=1\times9+2\times90+3\times(100-99)$
$a_{101}=1\times9+2\times90+3\times(101-99)$
…

따라서 마지막 항만 생각했을 때, 마지막 항의 일반항은 다음과 같이 표현할 수 있다.

$(l+1)\times\left\{N-(10^l-1)\right\}$

일반화

위 두 가지 경우를 합치면, 다음과 같이 일반항을 완성할 수 있다.

$$a_N=\left\{\displaystyle\sum_{k=1}^{l}{k\times(9\times10^{k-1})}\right\}+(l+1)\left\{N-(10^l-1)\right\}$$

급수식 정리

위 수식을 이용해서 반복문을 돌려서 문제를 풀 수도 있겠지만, 수열의 꼴을 자세히 보면 조금 더 식을 정리할 수 있을 것 같다. 위 수식은 복잡해 보이지만, 수열이 $\displaystyle\sum_{k=1}^{n}{kx^{k-1}}$ 꼴의 멱급수이기 때문에 적절한 미적분을 통해 단순화할 수 있을 것이다. 이때 $kx^{k-1}$은 $x^k$의 미분된 형태, 즉

$$kx^{k-1} = \frac{d}{dx}\left(x^k\right)$$

이므로 아래 또한 성립한다.

$$\displaystyle\sum_{k=1}^{n}{kx^{k-1}} = \frac{d}{dx}\left(\displaystyle\sum_{k=1}^{n}{x^k}\right)$$

이고, 기하급수 공식에 의해 다음과 같이 나타낼 수 있다.

$$= \frac{d}{dx}\left\{\frac{x\left(x^n-1\right)}{x-1} \right\}$$

이제 미분을 계산하면, 다음과 같이 나타낼 수 있다.

$$= \frac{n x^{n+1} - (n+1)x^n + 1}{(x-1)^2}$$

이제 $x=10$을 대입하고 양변에 9를 곱하고, $n$ 대신 $l$ 로 치환하면 다음과 같이 우리가 원하는 $\displaystyle\sum_{k=1}^{l}{k\times(9\times10^{k-1})}$ 의 닫힌꼴을 얻을 수 있을 것이다.

$$\displaystyle\sum_{k=1}^{l}{k\times(9\times10^{k-1})} = \frac{(9l-1)10^l+1}{9}$$

이것을 위의 $a_N$ 식에 대입하면 아래와 같이 표현할 수 있게 된다.

$$a_N = \frac{(9l-1)10^l+1}{9} + (l + 1)(N - 10^l + 1)$$

정리하면, 최종적으로 아래와 같이 표현된다.

$$a_N = (l+1)(N+1) - \frac{10^{l+1} - 1}{9}$$

구현 (Python)

이제 위 식을 코드로 구현해서 계산하기만 하면 된다.

from math import log10, floor

N = int(input())
l = floor(log10(N))

answer = (l + 1) * (N + 1) + ((1 - 10 ** (l + 1)) // 9)

print(answer % 1234567)

결과

마지막에 1234567로 나누는걸 까먹어서 왜 틀렸나 했다

실행 시간은 36ms가 걸렸다.

구현 (C++)

C++를 사용해서 속도를 극대화해보자.

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    long long N;
    cin >> N;

    int l = (int)log10(N);

    long long answer = (l + 1) * (N + 1) + (1 - (long long)pow(10, l + 1)) / 9;

    cout << answer % 1234567 << endl;

    return 0;
}

결과

실행 시간은 0ms가 걸렸다.

마무리

배열과 반복문을 이용해 직관적으로 풀어낼 수도 있는 문제이지만, 약간의 일반화 과정을 거쳐 일반항을 추론한다면 한 번의 계산으로 끝낼 수 있는 흥미로운 문제였다.