[백준/파이썬] 2877번 4와 7

https://www.acmicpc.net/problem/2877

2877번: 4와 7

기사 공부하랴, 텝스 하랴 소홀히 했던 알고리즘을 정말 오랜만에 다시 풀어보았다.

 

4와 7로 이루어진 수 중, n번째로 작은 수를 출력하는 문제다. 

 

단번에 아이디어가 떠오르지 않는데, 분명 패턴이 있을 것 같아서 찾을 때 까지 수를 계속 적어보았다.

문제에서 알 수 있듯, 이 문제는 이진수(0과 1로 이루어진 수)를 활용해 푸는 문제이다!

 

패턴을 살펴보자.

정수 1 = 이진수 1 = 4

정수 2 = 이진수 10 = 7

정수 3 = 이진수 11 = 44

...

 

이런 식으로 가다보면 뭔가 보일락 말락 할 것이다. 그럼 이제 패턴을 다시 살펴보자. 여기서 괄호는 생략이다!

정수 1 = 이진수 (1) = x

정수 2 = 이진수 (1)0 = 4 

정수 3 = 이진수 (1)1 = 7

정수 4 = 이진수(1)00 = 44

...

 

입력받은 정수에 1을 더해서 패턴을 이어 나간 것이다.

이제 다들 알 수 있을 것이다. 숫자 4를 이진수0으로 치환하고, 숫자 7을 이진수 1로 치환해서 풀면 된다.

import sys
#from collections import deque
#sys.setrecursionlimit(10**6)
from collections import Counter
input = sys.stdin.readline

if __name__ == "__main__":
    k = bin(int(input())+1)
    ans = ""

    for i in range(k.find('b')+2,len(k)):
        if k[i] == '0':
            ans += '4'
        elif k[i] == '1':
            ans += '7'
            
    print(ans)