[백준 - Python] 16974 - 레벨 햄버거

0.  문제 링크

 

 

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

16974번: 레벨 햄버거

---

1.  풀이 방법

 

 

해당 문제의 알고리즘은 구현이지만, 사실 가만 보면 분할 정복 문제와 다를 것이 없다.

방법은 별거 없다.

1. 맨 왼쪽 빵보다 왼쪽에 있으면 패티가 없다.
2. 중간 패티라면 왼쪽 패티 갯수를 넣는다.
3. 왼쪽 빵과 중간 패티 사이라면 분할 정복으로 왼쪽만 분할 정복으로 넣는다.
4. 오른쪽 빵과 중간 패티 사이라면 왼쪽 패티 갯수를 더하고 오른쪽을 햄버거를 분할 정복으로 넣어서 나온 값과 더한다.
5. 오른쪽 빵보다 오른쪽에 있으면 모든 패티의 갯수를 더한다.

레벨에 따른 패티와 층의 개수는 layer에 구현되어 있다.

해당 부분은 왜 저렇게 했는지는 직접 문제를 풀어봤다면 알 수 있을 것이다.

---

2.  코드

 

 

import sys

layer = [1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287,
         1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823,
         2147483647, 4294967295, 8589934591, 17179869183, 34359738367, 68719476735, 137438953471, 274877906943,
         549755813887, 1099511627775, 2199023255551, 4398046511103, 8796093022207, 17592186044415, 35184372088831,
         70368744177663, 140737488355327, 281474976710655, 562949953421311, 1125899906842623, 2251799813685247]

# layer = [1] * 51
# for i in range(1, 51):
#     layer[i] = layer[i - 1] * 2 + 1

def sol(n, x):
    if n == 0: return x     # n이 0이라면, 0~3개 중에 하나임
    elif x <= n: return 0       # 왼쪽 빵
    elif x == (l := layer[n]):      # 중간 패티
        return l // 2 + 1
    elif x < l:     # 중간 기준 왼쪽 패티들
        return sol(n - 1, x - 1)
    elif x < l * 2 - n:     # 중간 기준 오른쪽 패티들
        return l // 2 + 1 + sol(n - 1, x - l)
    else:       # 오른쪽 빵
        return l


n, x = map(int, sys.stdin.readline().split())
print(sol(n, x))

---

3.  마무리