[구현/수학] 백준 8741 이진수 합 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

8741번: 이진수 합

 

 

 

2. 문제 풀이

 이진수의 k자리 이하인 모든 자연수의 합을 이진수로 출력하는 문제입니다. 예를 들어, 3자리 이하인 이진수는 001, 010, 011, 100, 101, 110, 111로 모두 7가지입니다. 000은 0으로 자연수가 아니므로 제외됩니다.

 이를 경우의 수로 따져보면, 각 자릿수는 0 또는 1이 올 수 있으므로 2^k 이고 0을 제외하면 2^k -1이 됩니다.

 

등차가 1인 수열의 합: n * (n+1) / 2

 1부터 2^k -1까지의 합은 등차수열의 합 공식을 이용하면 쉽게 구할 수 있습니다.

 

 

 

3. 코드

k = int(input())

# 1부터 2^k -1까지의 합
n = 2**k-1
res = n*(n+1)//2

# 이진수로 출력
print(bin(res)[2:])

 파이썬의 bin() 함수를 이용하면 이진수로 변환할 수 있습니다. 앞에 이진수를 나타내는 0b만 [2:]로 제거해주고 출력합니다.