[BOJ][🟡5][백준#02877] 4와 7

문제 출처

BAEKJOON Online Judge #2877

문제

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

입력

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

출력

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

예제

예제 1

입력

1

출력

4

예제 2

입력

2

출력

7

예제 3

입력

3

출력

44

My Sol

ret = ''
for n in bin(int(input())+1)[3:]:
    ret += '4' if n=='0' else '7'
print(ret)

지금까지 풀었던 골드문제 중에 가장 짧고, 손 쉽게 푼 문제가 아닌가 싶다. 문제를 딱 보았을 때, 입력이 굉장히 크기 때문에 이분탐색을 먼저 생각했다가, 2진수와 관련된 문제인 것 같다고 느꼈다. DP스러운 접근으로는, N번째로 큰 수 뒤에 4와 7을 붙이면 2*N, 2*N+1처럼 접근할 수 있지 않을까를 생각했다. 그런데 순서가 조금은 달랐고, 입력으로 받은 N에 1을 더한 뒤 2진수로 변환하면, 앞의 1을 제외한 나머지의 규칙이 마치 00이 44, 101이 747처럼 진행됨을 확인할 수 있었다.

때문에 bin 함수 처리하여 앞에 붙는 bi와 1을 제외하기 위해 3번 index부터 뒤를 자른다. 이를 매번 순회하며 ‘0’이면 4, 아니면 7을 ret에 붙이며 나아간다. 그리고 이를 출력하면 되겠다. 굉장히 간단하게 풀 수 있는 문제였다.

결과

맞았습니다!!