출처
Koreatech Online Judge(링크)
문제이해
양의 정수를 1부터 일렬로 나열했을 때 (ex 123456789101112...) P번째에 오는 숫자를 구하는 문제이다.
문제접근
자리수가 1개인 수(1~9), 2개인 수(10~99), 3개인 수(100~999), ... 를 구분하여 계산한다
구현
아래와 같은 규칙이 있다.
- 자리수가 1개인 수를 모두 썼을 때는 길이가 9인 문자열이 생성된다.
- 자리수가 2개인 수를 모두 썼을 때는 길이가 90*2 = 180 인 문자열이 생성된다.
- 자리수가 3개인 수를 모두 썼을 때는 길이가 900*3 = 2700인 문자열이 생성된다.
만약 P 값으로 2889가 입력된다면, 그 수는 9+180+2700 이므로 세 자리 숫자 중 가장 마지막에 오는 숫자(999)일 것이다.
같은 방법으로, 임의의 P가 있을 때 이 수가 몇 자리 수로 이루어진 정수까지 썼을 때 나온 길이인지 계산할 수 있으며, 해당 자리 수를 가진 수 중 가장 작은 수까지 썼을 때 문자열의 길이도 구할 수 있다.
1부터 n까지 수를 일렬로 나열했을 때 문자열의 길이를 f(n)이라 한다면,
예를 들어, f(1000)과 f(10000)을 미리 계산할 수 있으므로, P가 이 사이의 값이라면 P는 네 자리 수까지 썼을 때의 값이다. 이 P값에서 f(1000)을 뺀 후 4로 나누고, 1000을 더하면, n값을 알 수 있는 것이다.
실행결과
코드
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1068/1068.cpp