백준 2885(Python) 풀이 : 초콜릿 식사

백준 2885 문제

백준 2885 링크 : https://www.acmicpc.net/problem/2885

백준 2885 풀이

이 문제를 어떻게 풀까 감이 잘 안 잡혀서, 여러 수를 직접 시도해 보면서 규칙성을 발견하려고 했다.

9 = 8 + 1 = 2^3 + 2^0 => 4번

10 = 8 + 2 = 2^3 + 2^1 => 3번

11 = 8 + 2 + 1 = 2^3 + 2^1 + 2^0 => 4번

12 = 8 + 4 = 2^3 + 2^2 => 2 번

이렇게 4번 정도 해보니까 규칙성을 조금은 감을 잡을 수 있었다. 결국 초콜릿을 작게 나눌수록, 전체적인 횟수가 늘어나는 구조다.

예를 들어, 12는 4까지만 빼주면 되기 때문에 2의 4제곱 -> 2의 2제곱까지만 나누는 것이고 2번이면 된다. 반면에 9는 2의 0승인 1까지 빼주어야 하기 때문에 2의 4제곱 -> 2의 0제곱까지 나눠야 하고, 횟수는 4번이 되는 것이다.

따라서, 초콜릿의 크기가 k보다 큰 2의 n제곱을 파악하고, 초콜릿의 크기가 딱 떨어지는 2의 n제곱을 파악하고 둘을 빼주었다.

# 2885

# 입력
import sys

k = int(sys.stdin.readline().rstrip())

# 크기 측정
n = 0
while True:
    if k <= 2**n:
        break
    else:
        n += 1

max_n = n

# 2의 거듭제곱으로 계속 빼기
while True:
    if k >= 2**n:
        k -= 2**n

    else:
        if k == 0:
            break
        else:
            n -= 1

min_n = n

# 출력
print(2**max_n, max_n - min_n)