#340 백준 파이썬 [1740] 거듭제곱

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

 

SOLUTION

제곱수의 합으로 이루어질 수 있는 수 중 작은 수부터 나열하는 문제다.

자세히보면 제곱은 정수의 조합으로 이루어져있다.

 

3^0 (이하 제곱만 나열) - 1개

1, 10 - 2개

2, 20, 21, 210 - 4개

3, 30, 31, 32, 310, 320, 321, 3210 - 8개

이를 쭉 지속해나가다 보면 증가량이 2의 배수 형태를 띔을 알 수 있다.

3^n + 3^n-1 .... 3^1, 3^0의 수는 n이 있느냐 없느냐에 따라

101010101011... 와 같이 표현할 수 있다.

 

ex) 11번째 수 = 1011 = 3^3 + 3^1 + 3^0

ex) 26번째 수 = 11010 = 3^4 + 3^3 + 3^1

ex) 100번째 수 = 1100100 = 3^6 + 3^5 + 3^2

PYTHON CODE

K = bin(int(input()))[2:] #2진법으로 변환하여 풀이
answer = 0

for i in range(len(K)):
    if int(K[i]) == 1: #1인 부분만 3**n을 더해줌
        answer += 3 ** (len(K)-i-1)
print(answer)