# [Gold V] 레벨 햄버거 #### [문제링크](https://www.acmicpc.net/problem/16974) ## 문제 설명 <p>상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-L 버거이다. 레벨-L 버거는 다음과 같이 만든다.</p> <ul> <li>레벨-0 버거는 패티만으로 이루어져 있다.</li> <li>레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, 패티, 레벨-(L-1)버거, 햄버거번으로 이루어져 있다. (L ≥ 1)</li> </ul> <p>예를 들어, 레벨-1 버거는 'BPPPB', 레벨-2 버거는 'BBPPPBPBPPPBB'와 같이 생겼다. (B는 햄버거번, P는 패티)</p> <p>상도가 상근날드에 방문해서 레벨-N 버거를 시켰다. 상도가 햄버거의 아래 X장을 먹었을 때, 먹은 패티는 몇 장일까? 한 장은 햄버거번 또는 패티 한 장이다.</p> ## 입력 <p>첫째 줄에 N과 X가 주어진다.</p> ## 출력 <p>첫째 줄에 상도가 먹은 패티의 수를 출력한다.</p> ## 풀이 #### N-버거에서 위에서부터 X를 먹었을 때 총 먹은 패티의 개수를 구하는 문제입니다. #### 패티의 개수는 재귀를 통해 구할 수 있으리라는 것은 구조를 통해 알 수 있습니다. 거기에서 중복되는 연산을 줄이기 위해 dp로 메모이제이션을 해서 풀면 됩니다. ``` c++ #include<bits/stdc++.h> using namespace std; long long cnt, n, x; long long dp[51][2]; // {총 개수, 패티의 개수} void getCnt(int depth) { // 총 번의 개수 계산 if(x==0) return; if(x-1>=0) x--; // 햄버거번 if(x-dp[depth-1][0]>=0) { // 레벨-1 버거 x -= dp[depth-1][0]; cnt += dp[depth-1][1]; } else { getCnt(depth-1); } if(x-1>=0) { // 패티 cnt++; x--; } if(x-dp[depth-1][0]>=0) { // 레벨-1 버거 x -= dp[depth-1][0]; cnt += dp[depth-1][1]; } else { getCnt(depth-1); } if(x-1>=0) x--; // 햄버거번 } int main() { ios::sync_with_stdio(0); cin.tie(0); dp[0][0]=dp[0][1]=1; for(int i=1;i<=50;i++) { dp[i][0] = dp[i-1][0]*2+3; dp[i][1] = dp[i-1][1]*2+1; } cin >> n >> x; getCnt(n); cout << cnt; } ```