https://www.acmicpc.net/problem/24514
문제 요약
- 숫자를 k 진법으로 표현
- X(n) : 1...n까지 k진법으로 표현해서 이어붙이기
- Y : X(1), X(2), ..., X(10^100)을 이어붙임
- Y에서 n번째 숫자를 찾기(최대 2*10^9)
접근법
- 숫자 범위를 직접 세어본다 : 누적합을 이용하다가 보면 대충 X(3만정도)까지 됨
- n 번째가 X(??) 얼마정도인지 찾아본다
- 완전탐색으로 찾아도 되고 : 최대 3만번 정도 순회
- upper bound 비슷하게 찾아도 됨 : n보다 크거나 같은 첫번째 위치 = n - 1의 upper bound
- X(??)에서 어디 숫자인지 찾아본다
- 완전탐색으로 찾아도 되고 : 최대 3만번 정도 순회
- upper bound 비슷하게 찾아도 됨
- 누적합 + 이분탐색을 위해서 두개의 배열 사용
- X의 배열 : 1, 2, 3, ... 누적합
- Y 배열 : X의 누적합
newbieski