[백준 16974] 레벨 햄버거 (C++)

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

 

문제 풀이

---

 

재귀 + dp 문제.

 

레벨과 남은 버거의 장 수를 매개변수로 받고 먹은 패티 수를 반환하는 재귀 함수를 작성한다.

레벨 0이라면 패티 하나를 먹으므로 1을 반환한다. 레벨 0이 아니라면 햄버거번, 레벨-(L-1) 버거, 패티, 레벨-(L-1)버거, 햄버거번을 먹게 된다. 햄버거 번을 먹고 남은 패티수가 있다면 레벨 L-1버거를 먹고, 레벨 L-1버거를 먹고 남은 패티 수가 있다면 패티를 먹고...의 순으로 햄버거 번까지 먹어 치운다.

레벨 L-1버거의 총 장 수보다 남은 장 수가 적다면 남은 장 수만큼만 먹을 수 있지만, 그렇지 않다면 레벨 L-1버거만큼 먹고 레벨 L-1버거를 먹을 수 있다.

먹을 때마다 먹은 수만큼 남은 장 수만큼 감소시키고, 먹은 패티 수를 증가시킨다.

 

레벨이 50까지이고 각 레벨마다 L-1 레벨이 2번씩 호출되므로 시간초과가 발생한다. 따라서 각 레벨마다 총 장수와 다 먹었을 때 먹은 패티 수를 저장하는 배열을 만들어 해당 값을 이용한다.

 

아래는 코드.

#include <iostream>
using namespace std;
long long* totalLayers;
long long* patty;

long long eatHamburger(int level, long long leftLayer)
{
	long long answer = 0;
	if (leftLayer == totalLayers[level])
	{
		return patty[level];
	}
	if (level == 0)
	{
		if (leftLayer == 0)
		{
			return 0;
		}
		else
		{
			return 1;
		}
	}
	else
	{
		leftLayer--;
		if (leftLayer == 0)
		{
			return answer;
		}
		else if (leftLayer >= totalLayers[level - 1])
		{
			answer += eatHamburger(level - 1, totalLayers[level-1]);
			leftLayer -= totalLayers[level - 1];
			if (leftLayer > 0)
			{
				answer++;
				leftLayer--;
				if (leftLayer == 0)
				{
					return answer;
				}
				else if (leftLayer >= totalLayers[level - 1])
				{
					answer+= eatHamburger(level - 1, totalLayers[level - 1]);
					leftLayer -= totalLayers[level - 1];
					if (leftLayer > 0)
					{
						leftLayer--;
					}
				}
				else
				{
					answer += eatHamburger(level - 1, leftLayer);
				}
			}
			else
			{
				return answer;
			}
		}
		else
		{
			answer += eatHamburger(level - 1, leftLayer);
		}
	}
	return answer;
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	long long layer;
	cin >> N >> layer;
	totalLayers = new long long[51];
	patty = new long long[51];
	totalLayers[0] = 1;
	patty[0] = 1;
	for (int i = 1; i < 51; i++)
	{
		totalLayers[i] = 2 * totalLayers[i - 1] + 3;
		patty[i] = patty[i-1]*2 + 1;
	}
	cout << eatHamburger(N, layer) << "\n";
	return 0;
}