백준/1790번/수 이어 쓰기2/골드5

Problem Link: https://www.acmicpc.net/problem/1790

문제 설명

Site: Baekjoon
Number: 1790
Category: Mathematics
Rank: Gold 5

숫자를 1부터 N까지 쭉 나열하였을때 k번째에 오는 숫자가 무엇인지 맞추는 문제입니다.

다음과 같은 방법을 사용하여 해결하였습니다.

자릿수가 1개인 수는 9개, 2개인 수는 90개, 3개인 수는 900개가 있으며, 각 자릿수 마다 숫자는 9, 180, 2700순으로 있습니다.

이를 통해 입력된 k번째 수의 자릿수와 숫자를 알 수 있으며, 해당 위치에서 몇번 가는지 계산한다면 답을 구할 수 있습니다.

문제의 예시를 통해 본다면 다음과 같습니다.

풀이 과정

23번째는 9보다 크고 90보다 작으니 자릿수가 2개입니다.

23에서 9를 뺀다면 14가 나오고, 14를 2로 나눈 나머지값 0을 offset에 넣습니다.

14를 자릿수만큼 나눈다면 7이 되고 이를 9에 더한다면 16이라는 숫자가 나오게 됩니다.

현재 위치가 가르키고 있는 곳은 6의 부분이고, 여기서 offset만큼 더한 위치가 k번째 숫자가 되게 됩니다.

예제에서 23번째는 6을 가르키며 0의 offset을 갖고있기 때문에 답이 6이 나오게 됩니다.

만약 24번째를 구해야 한다면 offset이 1이 나오게 되며, 16에서 1을 더한 17의 첫번째 숫자인 1을 반환하면 됩니다.

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

long long Digits[11];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int N, k, digit;
    cin >> N >> k;

    for(long long i = 1; i < 11; i++)
    {
        Digits[i] = Digits[i - 1] + i * 9 * (long long) pow(10, i-1);
        if (k <= Digits[i])
        {
            digit = static_cast<int>(i);
            break;
        }
    }

    int num = k - Digits[digit - 1];
    int offset = num % digit;
    num /= digit;

    num += pow(10, digit-1) - 1;

    if (offset == 0)
    {
        if (num > N)
        {
            cout << -1;
            return 0;
        }
        string str = to_string(num);
        cout << str[digit - 1];
    }
    else
    {
        num++;
        if (num > N)
        {
            cout << -1;
            return 0;
        }
        string str = to_string(num);
        cout << str[offset - 1];
    }

    return 0;
}