BOJ 1790 : 수 이어 쓰기 2

#BOJ 1790 : 수 이어 쓰기 2

1790번: 수 이어 쓰기 2

#풀이

n의 값이 너무 커서 string 으로 구현을 해서 구하기엔 시간초과가 뜬다...

 

1자리(1-9) 9개

2자리(10-99) 180개

3자리(100-999) 2700개

.

.

 

이렇게 구간을 정해서 k번째 있는 수가 어떤 구간에 있는지 확인

 

100 101 102

1,2,3/ 4,5,6/ 7,8,9 이렇게 보면  올림(3/3) = 1, 올림(2/3) = 1 올림(1/3) = 1  위에서 구했던 자리수를 이용해 해당 자릿수의 몇번째 숫자인지 확인 할 수 있다.

 

4 % 3 = 1, 5 %3 = 2, 6%3 = 0

idx = 6%3

idx = idx == 0 ? 3-1 : idx -1

나머지 연산을 통해 k번째에 있는 수를 확인할 수 있다.

 

#코드

#include<iostream>
#include<string>
#include<cmath>
using namespace std;

int n, k;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	long long idx = 9;
	cin >> n >> k;
	if (k <= 9 && n >= k) {
		cout << k << '\n';
		return 0;
	}
	else {
		k = k - 9;
		long long ten = 1; // 자릿수 확인
		for (int i = 2; i <= 9; i++) {
			ten = 1;
			for (int j = 2; j <= i; j++) {
				ten = ten * 10;
			}
			idx = 9 * i * ten;
			if (idx >= k) {
				idx = i;
				break;
			}
			k = k - idx; // 해당 자릿수의 몇번째 인지 확인
		}
		long long num = (int)ceil(k / (double)idx);
		long long num_idx = k % idx;
		if (ten + num - 1 > n) {
			cout << -1 << '\n';
			return 0;
		}
		string ans = to_string(ten + num - 1);
		num_idx = num_idx == 0 ? idx - 1 : num_idx - 1;
		cout << ans[num_idx] << '\n';
	}
	return 0;
}