[Python] 2877번 4와 7

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

2877번: 4와 7

---

 

22/10/07

 

 

약간의 아이디어가 있으면 쉽게 풀 수 있는 문제로, 사람에 따라 더 쉽게 느껴질 수도 있는 문제라고 생각한다.

---

 

문제 접근 방식:

 

 

문제 해결의 가장 큰 핵심은 이진수이다.

 

이 아이디어는 나열하다 보니 알게 되었다.

 

 

4
7
---- 한 자릿수(2개 있음)
44
47
74
77
---- 두 자릿수(4개 있음)
444
447
474
477
744
747
774
777
---- 세 자릿수(8개 있음)

 

 

7을 1로, 4를 0으로 간주하면 마치 4와 7이 채워지는 규칙이 이진수의 숫자가 늘어나는 모습과 매우 유사했기 때문이다.

 

먼저, 우리는 현재 입력받은 숫자를 통해 출력해야 되는 숫자가 몇 자릿수인지 알아야 한다.

 

예를 들어 8이면 세 자릿수를 출력해야 된다.

 

8을 입력받으면 447을 출력해야 되는데, 이는 세 자릿수 숫자 중에서 001에 해당이 된다.

 

다시 말해, 1을 이진수, 세 자리로 출력하면 되는 것이다.

 

규칙을 보면 한 자릿수는 2개, 두 자릿수는 4개, 세 자릿수는 8개,... 이렇게 2의 거듭제곱 꼴로 개수가 늘어남을 알 수 있는데, 이를 참고하여 입력받은 숫자에서 2의 거듭제곱을 차례대로 빼는 방식을 취해주었다.

 

그러다가 음수가 나오거나 0이 나오면 입력받은 숫자가 P자리 수에서 몇 번째에 위치해있는지 알 수 있으므로, 이를 이진수로 변환 후 1을 7로 변환, 0을 4로 변환하여 출력하도록 구현하였다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2877번 4와 7
# 그리디 알고리즘, 문자열
'''
접근 방법: 규칙 찾기
4
7
---- 한자리수 숫자(2개 있음)
44
47
74
77
---- 두자리수 숫자(4개 있음)
444
447
474
477
744
747
774
777
---- 세자리수 숫자(8개 있음)
'''
K = int(input())
num_of_digits = 1   # 출력하는 숫자의 자리수
while True:
    K -= 2**(num_of_digits)
    if K <= 0:
        K += 2**(num_of_digits)
        break
    num_of_digits += 1
    
K -= 1
print(bin(K).lstrip('0b').zfill(num_of_digits).replace('0', '4').replace('1', '7'))