[백준] 16974번 - 레벨 햄버거 / C++

문제

상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-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 버거에 있는 레이어의 수

 

코드

#include <iostream>

using namespace std;

int N;
long long X;
long long burger[51];
long long patty[51];

void init()
{
	int i;

	burger[0] = 1;
	patty[0] = 1;
	for (i = 1; i <= N; i++)
	{
		burger[i] = 1 + burger[i - 1] + 1 + burger[i - 1] + 1;
		patty[i]  = patty[i - 1] + 1 + patty[i - 1];
	}
}

long long ate(int n, long long x)
{
	if (n == 0)
		return x;
	if (x == 1)	
		return 0;
	else if (x <= 1 + burger[n - 1])
		return ate(n - 1, x - 1);
	else if (x == 1 + burger[n - 1] + 1)
		return patty[n - 1] + 1;
	else if (x <= 1 + burger[n - 1] + 1 + burger[n - 1])
		return patty[n - 1] + 1 + ate(n - 1, x - (1 + burger[n - 1] + 1));
	else
		return patty[n - 1] + 1 + patty[n - 1];
}

int main()
{
	cin >> N >> X;
	init();
	cout << ate(N, X) << endl;
	return 0;
}

 

코드에서 burger는 각 레벨에서 버거의 크기(=문자열의 길이)를 저장하고, patty는 각 레벨에서 패티의 개수(='P'의 개수)를 저장한다. 

다음은 레벨-0 버거부터 레벨-3 버거까지 나타낸 것이다. 먼저, n이 0이라면 버거는 패티 하나로 이루어지므로 x를 리턴한다. 이때 x는 0 또는 1이며 이것이 먹은 패티의 개수를 의미하기도 하기 때문이다. n이 1 이상이라면 x는 5개의 범위 중 x가 속한 범위에 따라 리턴 값이 달라진다.

1. 첫 번째는 무조건 햄버거 번이므로 먹은 패티의 개수는 0이다.
2. 첫 번째 레벨-(n - 1) 버거를 먹다 만 경우 맨 아래의 햄버거 번을 빼고(x - 1), 첫 번째 레벨-(n - 1) 버거의 어디까지 먹었는지 확인한다.
3. 레벨-n 버거의 중간에 위치한 패티까지 모두 먹은 경우에는 첫 번째 레벨-(n - 1) 버거의 모든 패티와 중간에 위치한 패티 하나까지 먹은 것이다.
4. 두 번째 레벨-(n - 1) 버거를 먹다 만 경우 레벨-n 버거의 중간에 위치한 패티까지 빼고, 두 번째 레벨-(n - 1) 버거의 어디까지 먹었는지 확인한다. 이때 중간의 패티까지는 모두 먹은 것이다.
5. 레벨-n 버거를 모두 먹은 경우에는 모든 패티를 먹은 것이다.

 

링크

16974번: 레벨 햄버거

inbdni/Baekjoon