코딩 테스트/백준 강의 연습편
시뮬레이션과 구현) 16974.레벨 햄버거
Carnival7
2022. 6. 9. 10:23
https://www.acmicpc.net/problem/16974
16974번: 레벨 햄버거
상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-L 버거이다. 레벨-L 버거는 다음과 같이 만든다. 레벨-0 버거는 패티만으로 이루어져 있다. 레벨-L 버거는 햄버거번, 레벨-(L-1) 버거,
www.acmicpc.net
# solution.
# d[i] : 레벨 i 인 햄버거의 길이. d[i]=1+d[i-1]+1+d[i-1]+1=2d[i-1]+3
# p[i] : 레벨 i 인 햄버거의 패티 개수. p[i-1]+1+p[i-1]=2p[i-1]+1
# go(n,x) : 레벨 n 버거에서 아래 x장 중 패티의 개수 반환
# if n>=1:
# x==1: 0
# 1<x<=1+d[n-1] : p[n-1]
# x=1+d[n-1]+1 : p[n-1]+1
# 1+d[n-1]+1<x<=1+d[n-1]+1+d[n-1] : 2p[n-1]+1
# x=1+d[n-1]+1+d[n-1]+1 : 2p[n-1]+1
n,x=map(int,input().split())
d=[0]*(n)
p=[0]*(n)
d[0]=1
p[0]=1
for i in range(1,n):
d[i]=2*d[i-1]+3
p[i]=2*p[i-1]+1
def go(n,x):
if n==0:
if x==0:
return 0
else:
return 1
else:
if x==1:
return 0
elif 1<x<=1+d[n-1]:
return go(n-1,x-1)
elif x==d[n-1]+2:
return p[n-1]+1
elif d[n-1]+2<x<=2*d[n-1]+2:
return p[n-1]+1+go(n-1,x-1-d[n-1]-1)
else:
return 2*p[n-1]+1
ans=go(n,x)
print(ans)