[Python] 백준 2885번: 초콜릿 식사

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

2885번: 초콜릿 식사

import sys
input = sys.stdin.readline


def solution():
    K = int(input())

    area = getArea(K)
    if K == area:
        print(area, 0)
    else:
        print(area, getSliceCount(area, K-area//2))


def getArea(n):
    area = 1

    while area < n:
        area *= 2

    return area


def getSliceCount(area, index):
    offset = area//8
    sliceCount = 2
    todo = [area//4]

    while True:
        nextTodo = []

        for idx in todo:
            if idx == index:
                return sliceCount
            nextTodo += [idx+offset, idx-offset]

        offset //= 2
        sliceCount += 1
        todo = nextTodo


if(__name__ == '__main__'):
    solution()

설명과 예시가 너무 부족하다고 느낀 문제이다. 최소한의 2의 배수의 넓이를 가진 직사각형의 초콜릿을, 최소한으로 잘라서 K를 만들어내라는 것이다.

가령 5가 들어왔다고 했을 때 취할 행동은 다음과 같다.

그러니까 3번 잘라서, 1과 4를 먹으면 된다.

 

그럼 패턴을 파악해보고자 가로 8 세로 4의 길이를 지니는 초콜릿을 순차적으로 갈라보자.

쪼개진 초콜릿에서 가능한 K값들을 나타낸다.

우선 1번 가른 것은 16과 16으로 나누어지지만, 16을 먹을 것이었으면 애초에 16 크기의 초콜릿을 먹으면 된다.

다시 패턴을 파악해보자면, left가 16, right가 32인 상태에서 이분탐색을 할 때의 mid값들이 가능한 K값이 되겠다.

 

사실 이분탐색은 비유였고, 필자는 오프셋을 조절해주면서 bfs를 돌리는 식으로 풀었다.

위 사진과 같은 경우에선, 처음에 offset이 4이고, todo에는 8(24를 의미함, 16+8 = 24)가 들어간다. 그럼 nextTodo에는 8에서 +- 4를 해준 4와 12가 들어가고, todo는 다음에 [4, 12]가 된다. 또한 offset도 1/2로 줄여야한다.

 

이러한 틀을 갖춘 bfs에서, sliceCount를 todo가 바뀔 때마다 1씩 늘려주고, todo를 순회할 때, 우리가 찾는 값과 비교하여 같으면 해당 상태에서의 sliceCount를 리턴해준다.