ABC 336 C번 복기 - 0,2,4,6,8로만 만든 숫자들 중 n번째 숫자를 찾는 놀라운 방법

C - Even Digits (atcoder.jp)

C - Even Digits

 

 

0,2,4,6,8로만 이루어진 모든 10진수 정수들을 오름차순으로 나열할 때,

 

N번째 숫자를 구하는 문제

 

N이 $10^{12}$까지니 다 해보면 당연히 시간 초과일거고

 

최초 몇가지를 한번 나열해보면?

 

0	0
2	1
4	2
6	3
8	4
20	10(5)
22	11(5+1 = 6)
24	12(5+2 = 7)
26	13(5+3 = 8)
28	14(5+4 = 9)

 

 

0,2,4,6,8,20,22,24,26,28...을 나열해보고 이들을 2로 나눠보니

 

0,1,2,3,4,10,11,12,13,14,...가 되는데..

 

이는 5진법을 0부터 차례대로 나열한 것과 마찬가지다.

 

이 때 0이 1번

 

1이 2번

 

2가 3번

 

3이 4번

 

4가 5번...

 

이라는거에 주의해서 만약 N번째 숫자를 찾고 싶다면..?

 

N에서 1을 빼고 N-1을 5진법으로 고친 다음.. 각 자리수들을 2배하면 된다.

 

10진수를 5진수로 고치는 방법은?

 

10진수를 2진수로 고칠때 2로 나눈 다음 그 나머지를 거꾸로 나열한 것과 마찬가지로..

 

5로 나누면서 나머지를 거꾸로 나열하면 된다.

 

이때 미리 2배해놓은 다음 저장한다면 편하겠지

 

#0,2,4,6,8로만 이루어진 수를 오름차순으로 나열할때, N번째 숫자
#0,2,4,6,8,20,22,24,26,28,...을 2로 나눠보면
#0,1,2,3,4,10,11,12,13,14,...
#0,1,2,3,4,5,(5+1),(5+2),(5+3),(5+4)
#따라서 반대로 생각해서 N-1을 5진수로 고쳐서 각 자리수를 2배하면 된다
n = int(input()) - 1

if n == 0:
    
    print(0)

else:

    m = []
    
    while n > 0:
    
        n,r = n//5,n%5
    
        m.append(2*r)
    
    m.reverse()
    
    print(''.join(map(str,m)))