[BOJ] 12755 - 수면 장애

https://www.acmicpc.net/problem/12755

BOJ - 수면 장애

문제 유형: 수학, 브루트 포스, 구현

문제 난이도: Silver IV

시간 제한: 1초

메모리 제한: 128MB

 

문제

수면 장애를 가진 강민이는 잠이 오지 않아 적잖은 고통을 느끼고 있다. 강민이는 잠이 오지 않을 때마다 속으로 양을 세고 있었는데, 오늘따라 백만 마리까지 세었는데도 잠이 오지 않았다.

한계를 느낀 강민이는 새로운 방법으로 수를 세기로 했다.

1부터 숫자를 쭉 이어 붙이면 다음과 같은 숫자열이 생성된다.

12345678910111213...

강민이는 이 숫자열을 한 숫자씩 떼어서 읽기 시작했다. 수면에 성공한 강민이는 다음날 일어나자마자 "N번째 숫자까지 읽었어!" 라고 기분 좋게 외쳤다.

과연 N번째 숫자는 무엇일까?

 

입력

첫째 줄에 N번째 숫자를 나타내는 N이 주어진다. (1≤N≤100,000,000)

 

출력

첫째 줄에 N번째 숫자에 해당하는 0~9 중 한 숫자를 출력하시오.

 

풀이

숫자 num을 셀 때마다,

1의자릿수라면 1씩 누적 길이가 늘어나고,

10의자릿수라면 2의 자릿수만큼 누적 길이가 늘어난다.

num을 추가할 때는 ln(num)+1만큼 누적 길이가 늘어난다.

 

만약에 이번에 숫자 num을 추가해서 누적 길이가 n 이상이 된다면, 숫자 num번의 어느 지점에서 중단되었다는 의미이다.

이 숫자를 문자열로 변환해서 n - num-1번 인덱스를 출력하면 정확히 어디까지 세었는지 알 수 있다.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[]) {
    int n;
    cin >> n;

    int lensum = 0;
    int curlen = 1;
    int next = 9;
    int streak = 0;

    int num = 1;
    while (true) {
        if (lensum + curlen >= n) break;
        lensum += curlen;
        streak++;
        num++;
        if (streak == next) {
            curlen++;
            streak = 0;
            next *= 10;
        }
    }

    string str = to_string(num);
    cout << str[n - lensum - 1] << "\n";

    return 0;
}