[백준]16974번 레벨 햄버거

 

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

---

문제의 햄버거는 위 그림과 같이 구성이 되었다. 그래서 우선 버거의 개수와 패티의 개수를 0~50 레벨 까지 미리 구해둔 후 재귀 함수를 이용해서 더 작은 햄버거로 내려가면서 먹은 패티 수를 구하면 되겠다고 생각했다. 경우의 수로는

1. 앞으로 먹어야 할 층의 개수가 딱 n-1 레벨 버거인 경우

2. 앞으로 먹어야 할 층의 개수가 n-1 레벌 버거의 층 수보다 작은 경우

3. 앞으로 먹어야 할 층의 개수가 n-1 레벨 버거의 층 수보다 큰 경우

로 나뉜다.

 

종료 조건이 아닐 경우 맨 밑의 B 를 먹어야 하기 때문에 먹어야 하는 층수를 감소시켜 주고 조건을 확인한다.

1 번의 경우 n-1 레벨 버거의 패티 수 만큼 추가 하고 답을 출력하면 된다.

2 번의 경우 n-1 이번 함수에서는 판단을 보류하고 n-1레벨 버거로 들어가 패티를 더 확인한다.

3 번의 경우 B + burger[n-1] + P 만큼 먹고 n-1레벨 버거로 들어가 패티를 더 확인한다.

 

종료 조건으로는 lower==0인 경우 문제에서 원하는 만큼 층을 먹었으므로 답을 출력하고 종료한다. n==0 인경우 0 레벨 버거로 패티1장을 추가로 먹고 끝이 날 경우이므로 먹은 패티수를 증가시키고 출력을 한다. 

 

#include <iostream>

using namespace std;
int N;
double X;
double burger[51] = { 0 };
double patty[51] = { 0 };
double ans=0;

void solve(int n,double lower) {
	if (lower == 0 ) {
		printf("%0.lf",ans);
		return;
	}
	else if (n == 0) {
		ans++;
		printf("%0.lf", ans);
		return;
	}
	lower--;
	if (lower == burger[n - 1]) {
		ans += patty[n - 1];
		lower -= (burger[n - 1]);
		solve(n - 1, lower);
	}
	else if (lower < burger[n - 1]) {
		solve(n-1, lower);
	}
	else if (lower > burger[n - 1]) {
		ans += patty[n - 1] + 1;
		lower -= (burger[n - 1] + 1);
		solve(n-1, lower);
	}
}

int main() {

	cin >> N >> X;
	burger[0] = 1; patty[0] = 1; 
	for (int i = 1; i <= 50; i++) {
		burger[i] = 2 * burger[i-1] + 3;
		patty[i] = 2 * patty[i-1] + 1;
	}
	solve(N,X);
}

 

---

저번 글에서 언급했던 16974번 문제였다. 역시 안풀리는 문제는 계속 코드를 붙잡고 있기보단 싹 지우고 다시 푸는것도 좋은 방법인 것 같다. 패티와 버거의 수를 미리 저장해두는 것 까지는 저번에 생각을 해뒀는데 막상 재귀로 코드를 짜려니 잘 안짜졌다. 차근차근 그림을 그려가면서 정확히 어떠한 조건에서 더 작은 문제로 분리할 수 있는지 생각해본다면 쉬운 문제인 것 같다.