[백준] 2877번: 4와 7 - Python

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

 

아이디어

• 그냥 2진수 생각하면 너무 쉬울 거 같다
• 4는 0 1은 7로 생각하고 풀어보자
• 우선 몇자리수인지 판단하자
  • 1자리 - 2개
  • 2자리 - 4개
  • 3자리 - 8개
  • 이런 식의 규칙을 가진다 중복합을 통해 몇자리인지 판단해아할듯
• 자릿수를 구한 후 그 자리수에서 몇번째의 수인지 한번 더 판단
  • 입력값 K에서 누적합을 진행합 값을 빼고 -1을 해준다
  • -1을 해줘야 하는 이유는 0000과 같은 경우도 하나의 경우로 쳐야하기 때문
• 몇번째 수인지 구했으면 이를 2진수 변환을 진행 자릿수도 구한 값으로 지정하여 생성
• 변환된 2진수를 0을 4로 1을 7로 변환한다.
• 그럼 끝~!

구현

# 뭐야 2진수로 생각하면 쉬울듯
# 몇자린지 구하고 거기서 몇번째인지 판단하면 끝

K = int(input())

# 몇자리인지 판단
length = 1
count = 0
while True:
    num_count = 2 ** length
    if count + num_count >= K:
        break
    count += num_count
    length += 1

# 그 자리수에서 몇번째인지 확인
index = K - count - 1

# 위 값 기반 2진수 생성
binary = bin(index)[2:].zfill(length)

# 0을 4로 1을 7로 변환
result = ''
for i in binary:
    if i == '0':
        result += '4'
    else:
        result += '7'

print(result)

 

마무리

그냥 문제를 보자마자 바로 어떻게 풀어야할지 그려졌다.

하지만 막혔던 부분이 있었는데 2진수 변환은 알았지만 이진수의 길이도 지정하는 법을 몰라 서치를 했다.

원하는 길이의 이진수로 변환하기 위해선 bin(변환할 값).zfill(원하는 길이) 기억하자

제트필~~~