[Python3] 백준 2877 - 4와 7

2877번: 4와 7

문제 설명

문제

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

 

입력

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

 

출력

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

 

알고리즘 분류

• 수학
• 구현

 

풀이 방법

출력되는 숫자를 차례대로 살펴보면 첫번째 숫자는 4, 두번째는 7, 세번째는 44, 네번째는 47, 5번째는 74, 6번째는 77, … 이진수와 비슷한 느낌을 받을 수 있다.

N		길이	출력	이진수	십진수
1	$$ N\le2^1 $$	1	4	0	0	$$1-(2^1-2)-1=0$$
2			7	1	1	$$2-(2^1-2)-1=1$$
3	$$ 2^1<N\le2^1+2^2 $$	2	44	00	0	$$3-(2^2-2)-1=0$$
4			47	01	1	$$4-(2^2-2)-1=1$$
5			74	10	2	$$5-(2^2-2)-1=2$$
6			77	11	3	$$6-(2^2-2)-1=3$$
7	$$ 2^1+2^2<N\le2^1+2^2+2^3 $$	3	444	000	0	$$7-(2^3-2)-1=0$$
8			447	001	1	$$8-(2^3-2)-1=1$$
9			474	010	2	$$9-(2^3-2)-1=2$$
10			477	011	3	$$10-(2^3-2)-1=3$$
11			744	100	4	$$11-(2^3-2)-1=4$$
12			747	101	5	$$12-(2^3-2)-1=5$$
13			774	110	6	$$13-(2^3-2)-1=6$$
14			777	111	7	$$14-(2^3-2)-1=7$$

4를 이진수에서 0, 7을 이진수에서 1로 생각한다면 이진수와 일대일로 대응시킬 수 있다.

길이가 1인 숫자부터 출력되므로, N을 이진수로 대입하기 위해서는 N에서 N을 변환시켰을 때의 숫자의 크기보다 길이가 작은 숫자들을 빼야한다.

이때 길이가 2에서부터 2씩 배로 늘어나므로 길이의 합은 고등학교 때 배운 등비수열의 합 공식으로 간단하게 구할 수 있다.

$$\frac{2(2^n-1)}{2-1}<N\le\frac{2(2^(n+1)-1)}{2-1}$$

위 식을 만족하는 n을 찾고, 길이가 n보다 작거나 같은 숫자들의 개수를 N에서 빼면 십진수에 해당하는 값을 얻을 수 있고, 이를 이진수로 변환하면서 0을 4로, 1을 7로 다시 대응시키면 원하는 값을 얻을 수 있다.

---

Python3

import sys
N=int(sys.stdin.readline())
n=0
while(2**(n+1)-2<N):
    n+=1
N-=2**n-1

ans=""
for _ in range(n):
    if N%2==0: ans=ans+"4"
    else: ans=ans+"7"
    N=N//2
print(ans[::-1])