백준 1790번 수 이어 쓰기 2 C++

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

 

분명히 답은 맞고 전혀 오래 걸릴 코드가 아닌데 계속 시간초과가 나서 고민을 많이 했는데 알고보니 while문 안의 tmp를 int형으로 선언해서 while문을 빠져나오지 못해 시간초과가 났다. 풀고나니 허무했다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	ll n, k;
	cin >> n >> k;
	ll len = 0;
	ll cnt = 0;
	ll ans = -1;

	string str = to_string(n);
	ll mul = 1;
	for (int i = 0; i < str.length() - 1; i++) {
		len += mul * 9 * (i + 1);
		mul *= 10;
	}
	ll start = pow(10, str.length() - 1);
	len += (n - start + 1) * str.length();

	if (k > len) {
		cout << ans;
		return 0;
	}

	mul = 1;
	while (true) {
		cnt++;
		ll tmp = mul * 9 * cnt;
		mul *= 10;
		if (k - tmp <= 0) {
			break;
		}
		k -= tmp;
	}

	ll a = (k - 1) / cnt;
	ll b = (k - 1) % cnt;
	start = pow(10, cnt - 1);
	ans = to_string(start + a)[b] - '0';

	cout << ans;
};