예전에 cses problem을 잠시 풀다가 멈추었었는데 다시 풀어보기 시작했습니다.
아래는 문제 링크입니다.
https://cses.fi/problemset/task/2431
CSES - Digit Queries
cses.fi
아이디 생성및 로그인은 매우 쉽게 할 수 있습니다.
먼저 문제를보면 123456... 의 증가하는 숫자 나열에서 어떤 위치 k의 값을 찾는 문제입니다. 이러한 시행은 q회 진행됩니다. 제약조건에 주의를 기울여보면 k의 맥시멈 값은 무려 10^18까지 입니다. 순차 탐색을 시켜보면 k의 값이 조금만 커져도 time limit을 맞출 수 없게 됩니다.
(물론 애초에 숫자나열을 만드는데 시간이 넘칠 거예요 ㅠㅠ)
그러면 초점을 바꾸어서 1,10,100 ... 이 자리의 숫자 길이를 고려해보았습니다. 패턴이 확실히 보이게 됩니다. 1의 자리 9개 10의 자리 90개..
그러고 나서 길이를 곱해보면 9,2*90,3*900...으로 나타나게 됩니다. 그래서 큰 k값이 있다고 하면 빼주면서 k의 크기를 줄일 수 있게 됩니다. 하지만 k값이 크면 빼주어도 k값은 여전히 큰데요..? (퍼포먼스가 안 나오잖아요 ㅠㅠ)
저희는 숫자길이에대한 정보를 알고 있습니다. 따라서 뺴준 k값에서 시작하는 숫자의 길이를 알고 있는 것이죠. 그렇다면 나누어서 몫과 나머지를 구하면 몫은 숫자를 지정할 수 있게 해 주고 나머지는 해당 문자열의 인덱스로 이용할 수 있게 됩니다.
위 아이디어로 퍼포먼스가 0.03초이내로 나오게 됩니다. 정답 파일은 올리지 않고 문제를 해결하시면 다른분들의 답변도 확인할 수 있습니다.