[C++]백준 - 1790번 문제

1790번: 수 이어 쓰기 2 (acmicpc.net)

1790번: 수 이어 쓰기 2

 

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~9 까지는 한 자리 수

10 ~ 99 까지는 두 자리 수

100~999까지는 세 자리수 ...

 

따라서 K가 9 이하면 한자리 숫자일 것이고,

K가 10 이상 9 + 90 * 2이하면 두 자리 숫자일 것이고..

 

이런 식으로 K가 몇자리 수의 정확히 어떤 수인지 파악해 낼 수 있습니다.

 

예를 들어, K가 23이라면 

 

우선 K가 9보다 크다면, 9를 빼보면

 

K = 14이 됩니다. K의 값이 90 * 2(자리 수) 이하면 K는 두 자리 수입니다.

 

K는 두 자리 수 중에 14 / 2번째 수입니다.

 

K는  두 자리 수 중 가장 작은 10을 포함하여 7번째 수 이므로 10 + 7 - 1 = 16

 

우리가 찾고자 하던 수는 16이며, 16 중 몇번 째 자리 수인지까지 알아내면 됩니다.

 

코드

---

#include <iostream>
#include <cmath>
int main()
{
	int N, K;
	scanf("%d %d", &N, &K);

	int digit = 1;
	int start = 1;
	long long level = 9;
    
    //K가 몇자리 수인지 찾아내기
	while (level < K)
	{
		K -= level;
		start *= 10;
		digit++;
		level = digit * 9 * start;
	}
	K--;
    
    //K가 정확히 어떤 수인지 알아내기
	int ans = start + K / digit;
	if (N < ans)
	{
		printf("-1");
		return 0;
	}

	//ans에서 해당 자리수만 걸러내기
	int place = pow(10, digit - (K % digit) - 1);

	ans /= place;
    ans %= 10;
	
	printf("%d", ans);
	return 0;
}

 

그 외

---