[백준 1790번] 수 이어 쓰기 2 풀이

1790번: 수 이어 쓰기 2

 

1 부터 N까지의 수를 이어붙였을 때, K번쨰 자리에 있는 문자를 출력하는 문제이다. 

먼저, K번째 자리에 있는 문자를 찾기 위하여 1번 부터 몇번까지의 수를 이어붙여야 하는지 찾아보자.

 

수의 특성에 따라,

1 ~ 9 까지의 수는 1자리 수들이고 9 * 10^0 = 9 개 이며,  9*10^0 * 1(문자의 자리수) = 9 개의 문자를 표현한다.

10 ~ 99 까지의 수는 2자리 수들이고 9 * 10^1 = 90 개 이며, 9*10^1 * 2(문자의 자리수) = 180 개의 문자를 표현한다.

100 ~ 999 까지의 수는 3자리 수들이고 9 * 10^2 = 900개 이며, 9*10^2 * 3(문자의 자리수) = 270개의 문자를 표현한다.

 

즉, idx+1 자리의 수들을 이어붙였을 때, 이어붙인 수들의 개수는 9*10^idx 개 이며, 이어붙인 문자들의 개수는 9*10^idx*(idx+1) 개가 된다.  이를 코드로 표현하면, 각 자리마다 이어붙인 문자의 개수 n은 다음과 같다. 

 

n = 9*(long long)pow(10, idx)*(idx+1)

 

따라서 idx를 1씩 늘려가면서 K번째 문자를 표현하기 위해 몇번째 자리의 수들까지 이어붙여야 하는지 구한다. 반복문을 빠져나온 후 K 값은 idx 자리까지의 수들을 모두 이어붙인 후 남은 문자의 수이다. 

 

long long n, idx = 0;
while ((n = 9*(long long)pow(10, idx)*(idx+1)) <= K) {
    K-=n;
    idx++;
}

 

반복문 내부에서 idx자리의 수들까지 모두 이어붙였으므로, idx+1 자리의 수들을 이어붙여 남은 K번째 문자에 도달해야 한다. 이 때, 이어붙이는 수는 10^idx 부터 시작한다. (3번째 자리의 수의 시작은 10^2 = 100으로, 아주 자연스럽다)

 

10^idx 부터 시작하여 M개의 숫자를 이어붙인 수가 반복문 이후의 남은 K번째 문자를 포함하고 있다고 가정해보자.

그렇다면, 초기의 K 번째 문자를 포함하기 위해 이어붙여야 하는 최소한의 수는 10^idx + M - 1 이 될 것이다.

 

한개의 수를 이어 붙일 때마다 idx+1 자리수만큼 문자의 개수가 늘어나므로,

M = (K를 (idx+1)로 나누어 올림한 값) 이 된다.

즉, 우리는 10^idx + M - 1 = 10^idx + (K를 (idx+1)로 나누어 올림한 값) - 1 까지의 수를 이어붙여야 한다. 

일반적으로, a를 b로 나누어 올림한 값은 (a+b-1)/b 로 구할 수 있기에 K를 (idx+1)로 나누어 올림한 값은 (K+idx)/(idx+1) 로 구한다.

 

long long num = (long long)pow(10, idx)+(K+idx)/(idx+1)-1;

 

이어붙여야 하는 최소한의 수를 num이라 할 때, num보다 입력된 N이 작다면 -1 을 출력한다.

그렇지 않으면, num을 문자열로 바꾼 것에서 특정 인덱스 (K+idx)%(idx+1) 를 출력한다.

 

전체 코드는 다음과 같다.

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
#include <tuple>
#include <queue>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

int main() {

    int N, K;
    scanf("%d %d", &N, &K);

    long long n, idx = 0;
    while ((n = 9*(long long)pow(10, idx)*(idx+1)) <= K) {
        K-=n;
        idx++;
    }
    long long num = (long long)pow(10, idx)+(K+idx)/(idx+1)-1;
    if (num > N) printf("-1");
    else printf("%c",to_string(num)[(K+idx)%(idx+1)]);
    return 0;
}