🐹 4와 7

1. 문제 링크

2877번: 4와 7

2. 코드

Python3 31120kb 40ms

count = [2**i for i in range(31)]
K = int(input())

num = 0
for i in range(1, 31):
    num += count[i]
    if K <= num:
        num_len = i  # K번째 숫자의 길이
        break

k_location = K - (num - count[num_len])
result = ''

div_num = 2
while num_len:
    n = k_location % div_num
    if n == 0 or n > (div_num // 2):
        result = '7' + result
    else:
        result = '4' + result
    num_len -= 1
    div_num *= 2

print(int(result))

3. 해설

먼저 K번째 숫자의 길이를 파악해줍니다. 여기서는 num_len

가장 작은 자리수 부터 값을 구해줍니다. 각 자리에는 4와 7만 들어갈 수 있으므로 경우의 수는 2의 num_len 제곱배 입니다.

확인하는 자리가 한 칸 앞으로 갈 때마다 div_num(나누어주는 수)에 2를 곱해줍니다. 이때 div_num으로 나눈 나머지가 div_num의 2분의 1배보다 작다면 ‘4’, 크다면(혹은 0으로 나누어 떨어진다면) ‘7’을 값에 연결해줍니다.

K번째 숫자의 길이만큼 반복해주고 문자열로 다뤘던 값을 int형으로 형변환 해줍니다.