1 minute read

16974번 : 레벨 햄버거

문제 링크

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

문제 설명

상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-L 버거이다. 레벨-L 버거는 다음과 같이 만든다.

  • 레벨-0 버거는 패티만으로 이루어져 있다.
  • 레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, 패티, 레벨-(L-1)버거, 햄버거번으로 이루어져 있다. (L ≥ 1)

예를 들어, 레벨-1 버거는 ‘BPPPB’, 레벨-2 버거는 ‘BBPPPBPBPPPBB’와 같이 생겼다. (B는 햄버거번, P는 패티)

상도가 상근날드에 방문해서 레벨-N 버거를 시켰다. 상도가 햄버거의 아래 X장을 먹었을 때, 먹은 패티는 몇 장일까? 한 장은 햄버거번 또는 패티 한 장이다.

입력

첫째 줄에 N과 X가 주어진다.

출력

첫째 줄에 상도가 먹은 패티의 수를 출력한다.

제한

  • 1 ≤ N ≤ 50
  • 1 ≤ X ≤ 레벨-N 버거에 있는 레이어의 수

문제풀이

다이나믹 프로그래밍을 활용하여 패티수를 출력할 수 있다.

N, X = map(int,input().split())
bur = [1] * 51            
pat = [1] * 51

for i in range(1, N+1):
    bur[i] = 2 * bur[i-1] + 3
    pat[i] = 2 * pat[i-1] + 1 

def eat(n, x):        
    # n이 0인 경우 패티가 1장 있으므로 x를 반환
    if n == 0:
        return x

    # n이 1이상이면 무조건 맨 밑은 햄버거번이므로 0을 반환
    if x == 1:
        return 0

    # x가 버거의 중간보다 작으면 n-1레벨에서의 재조회
    elif x <= 1 + bur[n-1]:   
        return eat(n-1, x-1)  

    # x가 버거의 중간을 먹으면 n-1레벨에서의 패티수+1을 반환
    elif x == 1 + bur[n-1] + 1:
        return pat[n-1] + 1
    
    # x가 버거 전체보다 작을때 n-1레벨에서의 패티수 + 1 + n-1레벨에서의 재조회 리턴값
    elif x <= bur[n-1] + bur[n-1] + 1 + 1:  
        return pat[n-1] + 1 + eat(n-1, (x-(bur[n-1]+2)))

    # 나머지 경우에는 n레벨의 패티를 출력
    else:                     
        return pat[n]

print(eat(N, X))

Comments

You May Also Enjoy