[BaekJoon] 16974번 레벨 햄버거 (Python) 문제 풀이 [Gold 5]

문제

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

 

어떻게 풀 것인가?

재귀 + 분할 정복 문제입니다.

먼저 레벨별 햄버거의 구조를 이해해야 합니다. 레벨-0은 패티(P) 하나이고, 레벨-L은 B + (L-1버거) + P + (L-1버거) + B 구조입니다. 예를 들어 레벨-1은 BPPPB, 레벨-2는 BBPPPBPBPPPBB이 됩니다.

각 레벨의 총 크기와 패티 수는 점화식으로 미리 구해둡니다. size[L] = 2 * size[L-1] + 3이고 patty[L] = 2 * patty[L-1] + 1입니다. N이 최대 50이라 크기가 엄청나게 커지므로 직접 문자열을 만들 수는 없고, 재귀로 접근해야 합니다.

핵심은 레벨-L 버거를 5개 구간으로 나눠서 X가 어디에 위치하는지 판단하는 것입니다.

| B(1장) | L-1 버거(size[L-1]장) | P(1장) | L-1 버거(size[L-1]장) | B(1장) |

 

X장을 먹었을 때 각 구간별로 분기합니다.

1. X ≤ 1 → 앞 번(B)만 먹은 것이므로 패티 0개
2. X ≤ 1 + size[L-1] → 앞 번 + 앞쪽 L-1 버거 일부를 먹은 것이므로, 앞 번 1장을 빼고 L-1 버거에 대해 재귀 호출
3. X ≤ 1 + size[L-1] + 1 → 앞 번 + 앞쪽 L-1 버거 전체 + 가운데 패티까지 먹은 것이므로, 앞쪽 L-1 버거의 패티 전부 + 가운데 패티 1장
4. X ≤ 1 + size[L-1] + 1 + size[L-1] → 뒤쪽 L-1 버거 일부까지 먹은 것이므로, 앞쪽 패티 전부 + 가운데 패티 + 뒤쪽 L-1 버거에 대해 재귀 호출
5. 그 외 → 전부 다 먹은 것이므로 해당 레벨의 전체 패티 수 반환

레벨-0에 도달하면 패티 1장이므로 1을 리턴하면서 재귀가 종료됩니다. 매 호출마다 레벨이 1씩 내려가므로 최대 50번만 재귀하면 되어 시간 내에 충분합니다.

 

코드

import sys
input = sys.stdin.readline
N, X = map(int, input().split())
size = [0] * (N + 1)
patty = [0] * (N + 1)
size[0] = 1
patty[0] = 1
for i in range(1, N + 1):
    size[i] = 2 * size[i - 1] + 3
    patty[i] = 2 * patty[i - 1] + 1
def solve(level, x):
    if level == 0:
        return 1 if x >= 1 else 0
    if x <= 1:
        return 0
    if x <= 1 + size[level - 1]:
        return solve(level - 1, x - 1)
    if x <= 1 + size[level - 1] + 1:
        return patty[level - 1] + 1
    if x <= 1 + size[level - 1] + 1 + size[level - 1]:
        return patty[level - 1] + 1 + solve(level - 1, x - 1 - size[level - 1] - 1)
    return patty[level]
print(solve(N, X))