[Tistory] 백준 수 이어쓰기 2 – 이분 탐색

원글 페이지 : 바로가기

https://velog.io/@embeddedjune/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89-%ED%8C%8C%EB%9D%BC%EB%A9%94%ED%8A%B8%EB%A6%AD-%EC%84%9C%EC%B9%98-1790-%EC%88%98-%EC%9D%B4%EC%96%B4-%EC%93%B0%EA%B8%B0-2 #if 1
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include #include
#include
#include
#define ll long long
#define ull unsigned long long
using namespace std;

int N, K;
ull low, high, ans;

int getStand(int n)
{
int ret = 0;
while (n > 0) n /= 10, ret++;
return ret;
}

ull getLen(int n)
{
int len = getStand(n);
ull ret = 0;
while (len > 0)
{
int tmp = n – pow(10, len – 1) + 1;
ret += len * tmp;
n -= tmp;
len–;
}
return (ret);
}
int main(void)
{
//ios_base::sync_with_stdio(false);
//cin.tie(nullptr);
//cout.tie(nullptr);
freopen(“input.txt”, “r”, stdin);

cin >> N >> K;
low = 1;
high = N;
ull len = getLen(N);
if (len < K) { cout << -1 << '\n'; return 0; } while (low <= high) { ull mid = (low + high) / 2; len = getLen(mid); if (len < K) low = mid + 1; else ans = mid, high = mid - 1; } char buf[20]; int s = sprintf(buf, "%d", ans); len = getLen(ans); cout<< buf[s - (len - K) - 1] - '0'<<'\n'; } #endif