[python] 백준 2885 초콜릿 식사

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

2885번: 초콜릿 식사

 

문제 해결

• n은 2의 거듭제곱식이다.
• n =1부터 k보다 커질때 까지 2를 계속 곱한다. (그 것이 최소 크기이다.)
• 모든 수는 2의 거듭제곱 수의 합으로 나타낼 수 있다.
• 따라서 k를 2의 거듭제곱 수의 합으로 표현할 때 최소 2의 지수를 보고 그 넓이의 초콜릿을 만드는데 몇 번 잘라야되는지 계산하면 끝

 

CODE

k = int(input())
n = 1
while n<k:
    n *= 2
ans_1 = n
cnt = 0

while n >1:
    n = n//2
    cnt += 1

x = k
i = 0
memo = [0]*(cnt+1) # 1,2,4,8,16... 넓이의 초콜릿 개수
while x >= 1:
    if x%2 == 1:
        memo[i] += 1
    else:
        memo[i] = 0
    x = x//2
    i += 1
for i in range(cnt+1):
    if memo[i] >= 1:
        ans_2 = cnt-i
        break

print(ans_1, ans_2)