[백준 2885] 초콜릿 식사(파이썬 풀이)

 

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

2885번: 초콜릿 식사

제출코드

import sys
input = sys.stdin.readline
k = int(input())
n,cnt= 1,0
while(n<k):
    n*=2
if n==k:
    print(n, 0)
else:
    ans = n
    # k에서 역으로 계산
    while(k>0):
        if k>=n:
            k-=n
        else:
            n//=2
            cnt+=1
    print(ans, cnt)

처음에는 전체 초콜릿에서 상근이가 원하는 크기가 될 때까지 잘라서 제일 작은 조각를 빼는 방법으로 코드를 짰다. 그랬더니 초콜릿 크기가 18일 때 무한루프가 돌며 시간초과가 발생했다. 16+2인 경우를 생각하지 못했기 때문이다.

상근이가 원하는 초콜릿의 크기 k를 구하는 대신 반대로 k에서 0이 될 때까지 조각을 빼기로 했다.

 

먼저 문제에서 전체 초콜릿을 크기는 항상 2의 제곱 형태라고 했으니 상근이가 먹고싶은 초콜릿보다 크거나 같으면서 그 크기가 2^n 형태인 크기를 찾았다.

while(n<k):
    n*=2

그리고 k가 2^n 형태이면 잘라내지 않고 다 상근이가 먹으면 되니 바로 k, 0을 출력한다.

if n==k:
    print(n, 0)

 k가 2^n이 아니라면 k가 0이 될 때까지 초콜릿을 조각내서 빼준다. 초콜릿을 조각낼 때는 cnt 변수를 1씩 더해준다.

while(k>0):
    if k>=n:
        k-=n
    else:
        n//=2
        cnt+=1