백준 1790번(수 이어 쓰기 2)

문제 링크

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

1234567891011121314151617181920212223...99100101102...

 

핵심 로직

1. 위의 수열에서 자리수별로 그 개수를 배열에 저장한다.
ex)

    1~9 : v[0] = 9  
    10~99 : v[1] = 180  
    100~999 : v[2] = 2700  
                 :
                 :

위의 식을 일반식으로 나타내면 아래와 같다.

2. 원래 수와 k 번째 숫자를 구한다.

여기서 말하는 원래 수는 위의 수열에서 2자리 수 이상의 수가 들어갈 때 등록되는 원본 수이다.

예를 들어 밑의 표에서 원래 주어진 수열에서 노란색 부분을 보자. 문제에서 주어진 수열은 1 이지만 그 1은 11에서 나온 것이다.

이 11을 원래 수라고 칭하겠다. 이 원래 수를 구하고 그 수 안에서 몇번째인지를 확인하면 된다.

 

소스코드

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

using namespace std;

int N, k, degit;
long long range;
vector <long long> v;

int main(void) {

    cin >> N >> k;

    // 자리수별 범위 구하는 소스
    for (int i = 0; i < 10; i++)
    {
        v.push_back(9 * (long long)pow(10, i) * (i + 1));
    }

    // 자리수 구하는 소스
    int tmp = N;
    while (tmp != 0)
    {
        tmp /= 10;
        ++degit;
    }
    //int ans1 = int(pow(10, -1));
    //int ans2 = int(pow(10, 0));
    for (int i = 0; i < degit - 1; i++)
    {
        range += v[i];
    }
    range += (N - (long long)(pow(10, degit - 1)) + 1) * degit;

    if (range < k) cout << -1 << '\n';
    else {
        long long cnt = 0;
        long long ran = 0;
        long long deCnt, deNum;
        for (int i = 0; i < v.size(); i++)
        {
            cnt += v[i];
            if (v[i] >= k) {
                cnt -= v[i];
                degit = i + 1;
                ran = k - cnt;
                deCnt = (long long)(pow(10, degit - 1)) + (ran-1) / degit;
                deNum = (ran + degit - 1) % degit;
                string result = to_string(deCnt);
                cout << result[deNum] << '\n';
                break;
            }
        }
    }

    return 0;
}