백준 16974번 레벨 햄버거

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

16974번: 레벨 햄버거

 

 

 

 

 

<접근방법>

모든 햄버거에 대해 문자열의 형태로 저장한다면 메모리 초과가 나옵니다.

문제에서 주어진 마지막 테케를 보면 알 수 있죠.

 

n번째 햄버거를 형상화 해봅시다.

 

b (n-1) p (n-1) b

          ^

 

이 때, x의 값에 따라서 답의 범위가 좁아진다는 것을 생각할 수 있습니다.

 

예로, x의 위치가 화살표가 가르키는 p라면 답은 1 + (n-1번째 햄버거 패티의 수) 가 되겠죠.

 

그러므로 x의 위치에 따른 값을 설정해줘야 합니다.

 

이 때, 필요한 값으로 레벨에 따른 햄버거의 크기와 패티이므로 값을 미리 저장해줍니다.

 

 

 

<느낀 점>

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int n;
long long x;
long long h[51];
long long p[51];

long long dfs(int n, long long x) {
	long long half = (h[n] - 1) / 2;

	if (n == 1) {
		if (x == 0) {
			return 0;
		}
		else if (x == 1) {
			return 0;
		}
		else if (x == 2) {
			return 1;
		}
		else if (x == 3) {
			return 2;
		}
		else {
			return 3;
		}
	}

	if (x == 1) return 0;
	else if (x == half) return p[n - 1];
	else if (x == half + 1) return p[n - 1] + 1;
	else if (x > half + 1) {
		return p[n - 1] + 1 + dfs(n - 1, x - (half + 1));
	}
	else {
		return dfs(n - 1, x - 1);
	}

}

int main() {
	cin >> n >> x;

	p[1] = 3;
	h[1] = 5;
	for (int i = 2; i <= n; i++) {
		p[i] = p[i - 1] * 2 + 1;
		h[i] = h[i - 1] * 2 + 3;
	}

	cout << dfs(n, x) << '\n';

	return 0;
}