레벨 햄버거 - 재귀문제

www.acmicpc.net/problem/16974

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 버거에 있는 레이어의 수

예제 입력 1 복사

2 7

예제 출력 1 복사

4

예제 입력 2 복사

1 1

예제 출력 2 복사

0

예제 입력 3 복사

50 4321098765432109

예제 출력 3 복사

2160549382716056

#include<iostream>
#include<vector>
#include<cstring>
#include <string>

using namespace std;

int n;
long long x;

long long hb[51];
long long p[51];

long long find(int n, long long x) {

	if (x == 1) {
		return 0;
	}
	else if (x == hb[n - 1]) {
		return find(n - 1, x - 1);
	}
	else if (x == 1 + hb[n - 1] + 1)  //번, n-1 햄버거, 패티
		return p[n - 1] + 1;
	else if (x <= 1 + hb[n - 1] + 1 + hb[n - 1]) //번, n-1 햄버거, 패티 ,n-1 햄버거    
		return 1 + p[n - 1] + find(n - 1, x - 1);
	else
		return 2 * p[n - 1] + 1;


}





int main() {


	cin >> n;
	cin >> x;

	hb[0] = 1; //전체 재료 
	p[0] = 1;  //패티의 개수 

	for (int i = 1; i <= n; i++) {
		hb[i] = 1 + hb[i-1] + 1 + hb[i-1] + 1;
		p[i] = p[i - 1] + 1 + p[i];
	}

	
	cout << find(n,x)<<endl;
	return 0;
}