[BOJ 1790] 수 이어 쓰기 2
- 문제풀이
문제
1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.
1234567891011121314151617181920212223...
이렇게 만들어진 새로운 수에서, 앞에서 k번째 자리 숫자가 어떤 숫자인지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다.
출력
첫째 줄에 앞에서 k번째 자리 숫자를 출력한다. 수의 길이가 k보다 작아서 k번째 자리 숫자가 없는 경우는 -1을 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 2sec | 64MB |
풀이
$N$의 범위가 1억까지다. 또한 메모리 제한이 64MB인데, 이는 char형 변수를 대략 6천만개 만들 수 있는 양이다. $k$의 값이 최대 10억인 상황에서 이어붙인 수를 직접 만드는 것은 불가능 하다고 판단할 수 있다. 그럼 직접 만들지 않고 수학적인 방법으로 이 문제를 해결해야할 것이다.
각 숫자의 자릿수를 기준으로 생각해보자. 길이가 $1$인 수의 갯수는 $1$ ~ $9$까지 총 $9$개 존재한다. 길이가 $2$인 수의 갯수는 $10$ ~ $99$까지 총 $90$개 존재한다. 조금 일반화하면, 길이가 $i$인 수의 갯수는 총 $9 \times 10^{i-1}$개 존재한다. 이를 활용하여 $k$의 값에 따라 정답 수의 길이를 유추해낼 수 있다. 아래 예시를 참고해보자.
- $0 + 1 \leq k \leq 0 + 9 \times 1$이라면, 정답 수 $n$의 길이는 $1$이다
- $9 + 1 \leq k \leq 9 + 90 \times 2$라면, 정답 수 $n$의 길이는 $2$이다
- $189 + 1 \leq k \leq 189 + 900 \times 3$이라면, 정답 수 $n$의 길이는 $3$이다
이를 일반화하여, 오른쪽 항(수 길이 $i$까지 작성하였을 때의 길이)을 $S_i$라고 하면,
- $S_{i-1} + 1 \leq k \leq S_{i-1} + 9 \times 10^{i-1} \times i$라면, 정답 수 $n$의 길이는 $i$이다
- $S_i = \sum_{j=1}^{i} 9 \times 10^{j-1} \times j$, $S_0 = 0$
라는 정보를 이용하여 정답 수의 길이를 알아내자. $N$의 범위가 최대 1억이었으니 수의 길이는 $i \leq 8$까지만 확인해보면 될 것 같다. 즉 for(int i = 1; i <= 8; ++i)로 정답 수 $n$의 길이를 유추할 수 있다는 것.
수의 길이를 알았으니 $n$이 어떤 수인지, 자릿수는 몇인지 알아내야한다. 이것도 생각보다 간단하다. 정답 수 $n$을 찾는 과정부터 예시를 보면서 이해해보자.
- 만약 $k=7$이라면, $0 + 1 \leq k \leq 0 + 9 \times 1$가 참이므로 $i = len(n) = 1$이며, $n$은 $1$의 자리 수에서 $7$번째 수인 $7$이다
- 만약 $k = 120$이라면, $9 + 1 \leq k \leq 9 + 90 \times 2$가 참이므로 $i = len(n) = 2$이며, $n$은 $2$의 자리 수에서 $\lceil \frac{(120 - 9)}{2} \rceil = 56$번째 숫자인 $65$이다
이걸 일반항으로 나타내면 $n = \lceil \frac{k - S_{i-1}}{i} \rceil + S_{i-1}$로 표현 가능하다. $i$를 유추했다면 $n$ 또한 바로 유추해낼 수 있다. 그럼 다음으로 $k$가 어떤 자릿수인지 알아내야할 것이다. 정답 수 $n$을 나눗셈을 통해 알아냈으니 자릿수는 모듈러를 활용하여 유추해낼 수 있다. 수의 길이가 길지 않으므로, 한 칸씩 넘어가보며 답을 찾아내도 된다.
여기서 추가적으로 한 가지를 더 고려해야 한다. 탐색 범위를 $i \leq 8$로 설정했었는데, 이러면 $n = 100\,000\,000$인 경우 오답을 받는다. 수의 길이가 $i=9$이기 때문이다. 이 예외 케이스만 한 번 더 고려하면 정답을 얻을 수 있다.
소스코드
Github Link : Source Code
참고 알고리즘 :