[백준-2877] 4와 7

문제

링크

풀이

import sys
input = sys.stdin.readline

k = int(input())

s = format(k+1, 'b')
s = s[1:]

print(s.replace('0', '4').replace('1', '7'))

풀이는 문제에 들인 시간에 비해 아주아주 간단했다.
4와 7로 두 숫자로만 이루어진 수를 구하는 문제였다.
처음에는 수 하나씩 구하면서 k번째가 나오면 출력하는 방법을 선택했다.
시간이 오래걸릴 거라 생각했는데 역시나 오래 걸려서 시간초과가 발생했다!
문제의 감을 잡지 못해서 결국 구글링의 힘을 빌렸다..
알아본 결과 사람들은 모두 이진법을 사용했다.
왜냐하면 수가 1번부터
4, 7, 44, 47, 77, 444, ...
이렇게 증가하는데 4를 0, 7을 1이라고 한다면
0, 1, 00, 01, 11, 000, ...
이렇게 이진수처럼 증가하기 때문이다. (그리고 어차피 수가 4와 7, 두 개밖에 없다.)
하지만 3, 6번처럼 0으로 시작하는 경우도 있으므로 앞에 1을 붙여주면
10, 11, 100, 101, 111, 1000, ...
2, 3, 4, 5, 6, ... 으로 증가하므로 k+1을 이진수로 변환하고,
슬라이스로 맨 앞 수를 없앤 다음 0이면 4, 1이면 7을 넣고 원하는 수를 구하면 되는 것이다.

이진법으로 풀 수 있다는 것을 눈치채지 못했다...
다시 풀어봐야겠고, 다음에 이렇게 이진법을 사용해서 문제를 풀 수 있다는 걸 알아서 다행인 것 같다.