백준 온라인 저지 1790 수 이어 쓰기 2

문제

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

1234567891011121314151617181920212223...

이렇게 만들어진 새로운 수에서, 앞에서 k번째 자리 숫자가 어떤 숫자인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 100,000,000)과,  k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다.

출력

첫째 줄에 앞에서 k번째 자리 숫자를 출력한다. 수의 길이가 k보다 작아서 k번째 자리 숫자가 없는 경우는 -1을 출력한다.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

#include <iostream>   using namespace std;   int getLen(int x) {//x번째 수까지 이어 썼을 때 길이를 구하는 함수     int len = 0;     for (int i = 1; i <= x; i *= 10)//일의 자릿수가 있는 수 + 십의 자릿수가 있는 수 ...         len += x - i + 1;     return len; }   int binary_search(int n, int k) {//이분 탐색 함수, getLen(x)<=k인 가장 큰 x를 찾기     int l = 1, r = 100'000'000, mid, ret;     while (l <= r) {         mid = (l + r) / 2;         if (getLen(mid) == k)             return mid;         if (getLen(mid) <= k) {             ret = mid;             l = mid + 1;         } else {             r = mid - 1;         }     }     return ret + 1; }   int main() {     int n, k, x;     cin >> n >> k;     if (getLen(n) < k)//n까지 이어 써도 k보다 짧은 경우         cout << -1 << '\n';     else {         x = binary_search(n, k);         cout << to_string(x)[k - getLen(x - 1) - 1] << '\n';         // x[총 길이 - (x-1 까지의 길이) -1(문자열이니까)]     }     return 0; } Colored by Color Scripter

cs