[BOJ/백준][Silver1] 1790 : 수 이어 쓰기2 (C++)

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

1790번: 수 이어 쓰기 2

 

 

[난이도] Silver1
[유형] 이분탐색

 

[풀이]
최대 N이 1억으로 너무 크기 때문에 1~N까지 순회하면서 k번째 수를 찾으면 시간초과가 난다.
이분 탐색을 이용해 low : 1 high : N+1 으로 시작해서 k번째 수가 포함된 숫자보다 1 작은 숫자를 범위를 좁혀가며 찾아준다.
그 숫자는 lo가 되게 되고
lo까지 숫자에 포함된 숫자의 개수가 정확히 K개이면 lo의 1의 자리수가 정답이고
K를 초과하면 lo+1(hi)에 K번째 수가 포함되어있으므로 그 수를 찾아준다.

 

#include <cstdio>
#include <string>
using namespace std;
int N,K;
int check(int m){
    int ret=0;
    int k=1;
    int i=10;
    for(;i<=m;i*=10,k++) ret+=(i-i/10)*k;
    ret+=k*(1+m-i/10);
    return ret;
}
int main(){
    scanf("%d%d",&N,&K);
    int lo=1;
    int hi=N+1;
    int cnt;
    while(lo+1<hi){
        int mid=(lo+hi)/2;
        if(check(mid)<=K) lo=mid;
        else hi=mid;
    }
    cnt = check(lo);
    if(cnt==K) printf("%c",to_string(lo).back());
    else {
        int r = K-cnt;
        string h;
        if(lo==N || to_string(hi).size() < r) {
            puts("-1");
            return 0;
        }
        printf("%c",to_string(hi)[r-1]);
    }
} 

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/1790.cpp