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

문제 링크

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

16974번: 레벨 햄버거

 

문제

풀이

고맙게도 예제에서 터무니없는 수의 X값이 주어진다.

50레벨 햄버거까지 가능한데, 50레벨 햄버거의 경우는 49레벨 햄버거 *2 + 3의 길이이고, 이게 중첩되다보면 엄청난 길이가 된다는 것을 알려준다. 약 2^50까지 증가한다.

따라서 직접 햄버거 구조를 만들어내는 것을 옳은 방법이 아니라는 것을 짐작할 수 있다.

 

궁금한 것은 X번째까지 먹었을 때 먹은 패티의 개수이다.

가상의 N레벨 햄버거를 생각했을 때, 절반을 기준으로 같은 구조가 반복된다.

햄버거[N] = 빵 햄버거[N-1] 패티 햄버거[N-1] 빵

 

즉 패티 부분이 N레벨 햄버거의 절반부분이고 이 부분을 기준으로 먹은 패티의 개수를 생각해본다.

 

여기서 len = N레벨 햄버거의 길이이다.

case1. N레벨 햄버거를 다 먹은 경우(마지막 빵 제외)  -> len-1 <= x

ans += N레벨 햄버거에 포함된 패티 개수

case2. 중간 패티보다 더 먹은 경우

햄버거[N-1] 패티 개수 + 햄버거[N-1]에서 x-(len/2+1)까지 먹은 경우 패티의 개수

case3. 중간 패티까지만 먹은 경우

햄버거[N-1] 패티 개수 + 1

case4. 나머지(1개 이상인 경우만 -> 한개인 경우는 빵을 먹은 경우)

햄버거[N-1]에서 x번째까지 먹은 경우

 

x와 len값을 비교해서 이렇게 총 4가지 케이스로 분류가 된다.

N-1레벨 햄버거에서 x번째까지 먹은 경우를 잘 return 해준다고 보장했을 때 재귀식이 성립한다.

햄버거의 길이는 항상 홀수이므로 len/2+1을 middle값으로 설정한다.

x가 1보다 작은 경우는 무시한다.(n=0인 경우, len == 1이므로 앞에서 처리된다) -> base condition

 

코드

#include <bits/stdc++.h>

#define endl "\n"

using namespace std;

long long N, X;
long long Paty[52];
long long Len[52];
long long ans;

void func(long long n, long long x) {
	
	long long len = Len[n];

	if (len-1 <= x) ans += Paty[n];
	else if (len / 2 + 1 < x) {
		ans += Paty[n - 1] + 1;
		func(n - 1, x - (len / 2 + 1));
	}
	else if(len/2+1==x) ans += Paty[n - 1] + 1;
	else if (1 < x) {
		func(n - 1, x - 1);
	}
}
void Solve() {
	cin >> N >> X;
	Paty[0] = 1;
	Len[0] = 1;
	for (int i = 1; i <= N+1; i++) {
		Paty[i] = Paty[i - 1] * 2 + 1;
		Len[i] = Len[i - 1] * 2 + 3;
	}
	
	func(N, X);
	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	freopen("input.txt", "r", stdin);
	Solve();
	return 0;
}

 

배열 크기를 51로 했다가 쓰레기값이 들어가서 삽질 하루종일 했다.