[BOJ 2877] 4와 7

문제 링크 : https://www.acmicpc.net/problem/2877

문제

창영이는 4와 7로 이루어진 수를 좋아한다. 창영이가 좋아하는 수 중에 K번째 작은 수를 구해 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 K(1 ≤ K ≤ 10⁹)가 주어진다.

출력

첫째 줄에 창영이가 좋아하는 숫자 중 K번째 작은 수를 출력한다.

제한

시간 제한	메모리 제한
1sec	128MB

---

풀이

$4$와 $7$로만 이루어진 숫자들을 크기순으로 나열했을 때 $K$번째 수를 찾는 문제다. 각 자릿수에 들어갈 수 있는 숫자가 $4$와 $7$로 총 $2$개씩이므로, 자릿수가 늘어남에 따라 가능한 숫자의 개수는 $2$의 거듭제곱 형태로 증가한다.

문제 해결을 위해 우선 $K$번째 숫자가 몇 자리 수인지 파악해야 한다. $i$자리 숫자의 개수는 $2^i$개이므로, $i$자리 이하의 숫자들의 총 개수는 다음과 같은 등비수열의 합으로 구할 수 있다.

\[\sum_{j=1}^{i} 2^j = 2^{i+1} - 2\]

사용자로부터 입력받은 $K$에 대하여, $2^{i+1} - 2 \geq K$를 만족하는 최소의 $i$를 찾으면 그것이 $K$번째 숫자의 자릿수가 된다.

자릿수를 결정했다면, 해당 자릿수의 숫자들 중에서 몇 번째에 위치하는지를 계산한다. $i$자리 숫자들 중에서의 순서는 $K - (2^i - 2)$와 같은 방식으로 구할 수 있다. 이때 $4$를 $0$, $7$을 $1$로 대응시키면 이는 이진수 체계와 정확히 일치하게 된다. 따라서 결정된 순서 값을 이진수로 변환하여 각 비트가 $0$이면 $4$를, $1$이면 $7$을 출력함으로써 정답을 도출할 수 있다.

$K$의 최대 범위는 $1\,000\,000\,000$이며, 이는 $2^{30}$보다 약간 작은 값이다. 따라서 자릿수는 최대 $30$ 내외로 결정되며, 반복문을 통해 자릿수 파악 및 각 자리의 숫자를 결정하는 과정은 $O(\log K)$의 시간 복잡도로 매우 빠르게 수행 가능하다.

소스코드

Github Link : Source Code

참고 알고리즘 :