[백준 1790] 수 이어 쓰기 2, C++

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

1790번: 수 이어 쓰기 2

 본 문제는 1 ~ n 까지의 수를 이어서 썼을 때 길이를 구하고 k의 위치의 값을 출력하는 문제다. n의 최대값이 매우 크기 때문에 실제로 값을 구해서 찾는 것은 불가능 하다. 따라서, k와 인접한 위치를 찾아서 출력하는 방식을 이용해야 한다. 이때, 이분 탐색을 이용하면 빠르게 답을 구할 수 있다. 예를 들어 n = 20 일 때,

1. 우선 n까지의 길이가 k보다 짧을 경우를 예외처리 한다. 
2. 1 ~ 9 까지의 길이를 구하고 10 ~ 20까지의 길이를 구한다.
3. 그리고 k에 인접한 수를 찾는다.
4. k 보다 작은 수를 구하도록 코딩을 하였다.
5. 그렇기 때문에 k 보다 커지는 순간까지 추가로 구해야 한다.
6. 이제 내가 찾아야하는 위치는 인접한 수의 길이에서 k보다 작은 길이를 빼고
7. 찾아야 하는 위치을 더하면 된다.
8. 이때, 배열의 인덱스를 생각하면서 추가로 1을 뺀다.

#include <cstdio>
#include <string>
 
using namespace std;
 
int n;
long long k;
int ans;
 
long long cal_length(int x) {
    // 1 ~ 9 : 9 * 1
    // 10 ~ 99 : 90 * 2
    // 100 ~ 999 : 900 * 3
    //     ....
    long long n_length = 0LL;
    long long n_size = to_string(x).size();
    for (long long add = 9LL, len = 1LL; len < n_size; add *= 10, len += 1) {
        n_length += add*len;
    }
    int start = 1;
    // ~ n
    for (int i = 1; i < n_size; i++) {
        start *= 10;
    }
    return n_length += n_size * (x-start+1);
}
 
void cal (int start, int end) {
    if (start >= end) return;
    int mid = (start + end) / 2;
    if (cal_length(mid) > k) {
        cal(start, mid-1);
    }
    else {
        ans = mid;
        cal(mid+1, end);
    }
}
 
int main() {
    scanf("%d %lld", &n, &k);
    long long n_length = cal_length(n);
    if (n_length < k) {
        printf("-1\n");
        return 0;
    }
    cal(1, n);
    long long ans_length = cal_length(ans);
    string s = to_string(ans);
    // (ans_length < k) to
    // (k < ans_length)
    while (ans_length < k) {
        ans += 1;
        s += to_string(ans);
        ans_length += to_string(ans).size();
    }
    printf("%c\n", s[s.size() - ans_length + k) - 1]);
}