수 이어 쓰기 2

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

1790번: 수 이어 쓰기 2

 

 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)

범위가 엄청 크다.

이분 탐색을 이용해서 풀어야한다.

 

<calc 함수>

길이를 어떻게 구할까?

n이 115 라고 생각해보자.

 

숫자 하나 -> 9개 ( 9 - 1 + 1)

숫자 두개 -> 90개 (99 - 10 + 1) 

숫자 세개 ->  900개 (999 - 100 + 1)

 

n이 999보다 작다면

115 - 100 + 1 = 16

 

9  * 1 + 90 * 2 + 16 * 3을 하면 길이가 구해진다.

 

<이분 탐색>

left = 1, right = n을 두고 시작한다.

mid 일 때의 길이를 구하고,

 

k가 더 크면

left = mid + 1

작거나 같으면

ans = mid;

right = mid - 1;

 

<마지막>

k 번째를 포함한 숫자 n을

to_string으로 바꾸고,

s[s.length() - (l - k) - 1]

 

<소스 코드>

#include <iostream>
#include <string>
 
using namespace std;
 
long long calc(int n)
{
    long long ans = 0;
    // start는 1, 10, 100 ... 
    // len은 한 자리, 두 자리, ...
    for (int start = 1, len = 1; start <= n; start *= 10, len++)
    {
        int end = start * 10 - 1;
        if (end > n)
        {
            end = n;
        }
        ans += (long long)(end - start + 1) * len;
    }
    return ans;
}
 
int main()
{
    int n;
    long long k;
    cin >> n >> k;
 
    // 그 숫자로 만들 수 있는 길이보다 k가 큼
    if (calc(n) < k)
    {
        cout << -1 << '\n';
        return 0;
    }
 
    int ans = 0;
    int left = 1;
    int right = n;
 
    while (left <= right)
    {
        int mid = (left + right) / 2;
        long long len = calc(mid);
 
        if (len < k)
        {
            left = mid + 1;
        }
        else
        {
            ans = mid;
            right = mid - 1;
        }
    }
 
    string s = to_string(ans);
    long long l = calc(ans);
    cout << s[s.length() - (l - k) - 1] << '\n';
    return 0;
}