[백준/16974/파이썬] 레벨 햄버거 - 재귀

---

소스코드

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):        

    if n == 0:

        return x

    if x == 1:

        return 0

    elif x <= 1 + bur[n-1]:   

        return eat(n-1, x-1)  

    elif x == 1 + bur[n-1] + 1:

        return pat[n-1] + 1

    elif x <= bur[n-1] + bur[n-1] + 1 + 1:  

        return pat[n-1] + 1 + eat(n-1, (x-(bur[n-1]+2)))

    else:                     

        return pat[n]

print(eat(N, X))

---

알고리즘

처음에 문제에서 제시한대로 문자열을 가지고 인덱싱을 이용하여 풀었는데 메모리 초과가 났다.

그래서 다른 사람의 풀이를 참고했는데 갯수를 가지고 조건에 따라 경우를 나누어 재귀를 이용하여 풀었다.