[BOJ 24514] 백준 24514번 - n번째 숫자 찾기

		2022 ICPC Sinchon Winter Algorithm Camp Contest 풀이
A		[BOJ 24510] 시간복잡도를 배운 도도
B		[BOJ 24509] 상품의 주인은?
C		[BOJ 24511] queuestack
D		[BOJ 24512] Bottleneck Travelling Salesman Problem (Small)
E		[BOJ 24513] 좀비 바이러스
F		[BOJ 24514] n번째 숫자 찾기
G		[BOJ 24515] 히히 못가
H		[BOJ 24516] 잘 알려진 수열 구하기
J		[BOJ 24517] 카드 게임과 쿼리
K		[BOJ 24519] Bottleneck Travelling Salesman Problem (Large)

1. 문제

$24514$. n번째 숫자 찾기 (2022 ICPC Sinchon Winter Algorithm Camp Contest F번)

백준 24514번 - n번째 숫자 찾기 (https://www.acmicpc.net/problem/24514)

2. 풀이

$YJ_k$에서 $N$번째 숫자를 찾으려면, 다음과 같은 총 세 가지 작업이 필요하다.

1. $N$번째가 어떤 $X_K(i)$에 포함되는지 알아낸다.
2. 그 $X_K(i)$에서 어떤 수를 나타낸 범위에 포함되는지 알아낸다.
3. 그 수를 $k$진법으로 나타낸 자리들 중 어떤 수인지 알아낸다.

$1$과 $2$를 하기 위해 이분탐색을 사용한다. 이때, 각 $X_K(i)$의 길이를 구하고 그 누적합을 배열에 저장해야 하는데, $N$번째 자리를 구하는 경우 $X_K(i)$에서 $i$는 $\sqrt{N}$이면 충분하다. (이에 대한 명확한 증명은 발견하지 못했다. 다만, 여러 시행착오를 통해 그렇게 추측하였다.)

따라서 $N\leq 20억$이므로, $\sqrt{20억}=44,730$ 정도 크기의 배열을 만들고, $X_K(i)$의 길이의 합을 저장하고(코드 상의 cnt vector), 이들을 누적시킨 누적합도 저장한다(코드 상의 cnt_sum vector).

$X_K(i)$ 누적합에서의 이분탐색으로 $1$을 수행하고, $X_K(i)$에서의 이분탐색으로 $2$를 수행하고, 진법변환으로 정답을 찾아내면 된다. (방법은 어렵지 않으나 이분탐색 구현이 까다로워서 바로 코드를 참고하는 게 좋은 방법인 것 같다.)

3. 채점 결과

4. 회고

이분탐색 구현에서 많은 실수를 해서 바로잡느라 엄청 고생했다. 첫번째 이분탐색때 right를 그냥 $\sqrt{N}$으로 하면 WA를 받아서 적당히 +10정도를 해주었다.

5. 코드