백준(BOJ) 16974번 레벨 햄버거

문제 : https://www.acmicpc.net/problem/16974

16974번: 레벨 햄버거

 

풀이 :

 

우선 hb [n] 은 n번째 레벨의 전체 재료의 수고 p [n] 은 p번째 레벨의 패티 수로 각 레벨의 전체 재료와 패티 수를 구한다.

 

그리고 x의 갯수에 따라 이전 레벨에서 처리하도록 넘겨주거나 그 값이 확실하다면 바로 반환하도록 하였다.

 

x 가 1이라면 무조건 햄버거 번이니 0을 반환하고

 

x 가 중앙에 오는 패티라면 전에 패티 + 중앙 패티가 답이 될 것.

 

 

 

코드 ( C++ )

	#include <iostream>
	using namespace std;
	int n;
	long long x;
	// 전체 재료
	long long hb[51];
	//패티 수
	long long p[51];
	long long solve(int n, long long x)
	{
	if (n == 0) {
	if (x == 0) return 0;
	else if (x == 1) return 1;
	}
	if (x == 1)
	return 0; // 무조건 햄버거 번
	else if (x <= 1 + hb[n - 1])
	return solve(n - 1, x - 1);
	else if (x == 1 + hb[n - 1] + 1)
	return p[n - 1] + 1;
	else if (x <= 1 + hb[n - 1] + 1 + hb[n - 1])
	return 1 + p[n - 1] + solve(n - 1, x - 1 - hb[n - 1] - 1);
	else
	return 2 * p[n - 1] + 1;
	}
	int main()
	{
	cin >> n >> 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 - 1];
	}
	cout << solve(n, x) << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub