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

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

다시 돌아온 다이나믹 프로그래밍입니다. 해당 문제를 풀때 굉장히 오랜시간 고민을 했습니다. 약 1시간정도를 고민했는데요. 중간에 어떤식으로 풀어야겠다 라는 방법이 떠올랐지만, 코드에 그대로 적용하기까지에 시간이 오래걸렸습니다.

왜냐하면, 처음에는 엄청 쉬워보였거든요. 그냥 단순히 햄버거 쌓는 규칙을 찾는줄 알았으나... 그게 아니고, 한단계씩 위의 햄버거를 보면서 문제를 해결하는 것이었던겁니다.

그래서, 재귀라는 것을 바로 생각하지 못하고 이리 저리 돌리면서 생각하다가 천천히 그림을 그려보니까 이렇게 구해야겠다고 생각을 했습니다.

첫번째 레벨 0는 단순히 패티 한장으로 이루어져 있습니다. [ p ] 이런식으로 말이죠.

두번째 레벨 1은 앞 뒤로 햄버거 번이 붙고,[b, p, b] 이런 상태가 되겠죠?

번과 패티 사이에 이전에 있던 버거가 붙습니다. [b, p, p, p, b] 가 되어버립니다.

문제에서도 이에 관련된 규칙을 알려줍니다. 

레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, 패티, 레벨-(L-1)버거, 햄버거번으로 이루어져 있다.  

오랜만에 좀 멋진 효과를 써봤습니다. 자기전이라 졸려서 그런가봐요. 어쨌든, 이런식으로 규칙이 나열되어 있어서 해당 문제를 해결할 때 어떻게 풀어야할까 고민을 했습니다.

일단 가장 먼저 떠오른 것은 패티의 개수를 구하는 것이기 때문에, 각 레벨당 패티의 개수를 구하는 것입니다. 그 값을 이용해서 문제를 해결할 것이기 때문에, 전체를 다 저장해두는 것이죠? 그것이 DP니까.

여기까지는 아주 수월합니다. 왜냐하면 문제에 저렇게 대문짝만하게 적혀있으니까요. 그럼 여기까지는 오케이인데, 이제 과연 어떻게 문제를 해결할 것인가? 생각해보면, 레벨(L-1)이 두개가 가운데 패티 하나를 두고 나눠져 있습니다.

그렇다는 얘기는? 패티를 기준으로 값을 구할 수 있지 않을까? 여기까지는 아주 잘 생각을 했습니다. 

여기까지는 그랬는데, 이후에 어떻게 구현을 해야할지 감이 안잡혔습니다. 어떻게 해야할까?를 글자를 끄적이면서 생각해보다가 갑자기 생각이 났습니다.

어차피 한칸 위 레벨의 햄버거가 아래 레벨의 햄버거로 내려가서 햄버거의 번이 앞에만 붙여 나오는거 하나 그리고 뒤에 붙여나오는거 하나. 이런식입니다. 물론 패티가 가운데 끼는것도 아주 중요합니다.

그렇다면 이 햄버거를 이쁘게 쪼갤수가 있다는 것입니다.

만약 원하는 햄버거의 어디 길이까지가 나왔을때 기준을 잡을 수 있다는 것입니다. 제가 쓰고도 말이 잘 이해가 안가는데 기준을 먼저 나눠보겠습니다.

원하는 길이가 해당 햄버거의 어느정도 길이까지인지 판단을 해야합니다.

아까도 말했듯이 패티 기준으로 앞에 햄버거는? 햄버거 번을 하나 붙인 이전 햄버거 입니다.

그렇다면? 이전 햄버거의 길이(hamburger[level-1] + 1)이 내가 원하는 숫자랑 같다면? hamburger[level - 1]의 패티 개수만큼을 리턴하면 됩니다. 이런식으로 구하면 되겠죠? +1을 해준이유는 햄버거 번이 추가되기 때문입니다.

그렇다면 이전 햄버거의 길이(hamburger[level-1] + 1)이 내가 원하는 숫자보다 작다면? 다시 위의 레벨을 살펴보는 재귀로 돌아가게 됩니다.

그렇다면 또, 이전 햄버거의 길이(hamburger[level - 1] + 2) 라면? 패티까지 포함이 되겠죠? 그렇다면 똑같이 이전 햄버거의 패티 개수를 리턴해주면 됩니다.

그렇다면 이전 햄버거의 길이(hamburger[level - 1] * 2 + 2) 보다 작거나 같다면?  현재 앞에 있는 햄버거와 가운데 패티까지는 당연하게 포함이고, 뒤에 있는 햄버거의 길이는 다시 이전 햄버거로 재귀시켜버리는 것입니다.

넘어가면 이전 햄버거의 패티개수 * 2 + 1을 해줘버리면 됩니다.

이렇게 다양한 조건을 모두 구해서 재귀를 돌려버리면 됩니다. 이렇게 생각이 되어서 구현할라하는데 굉장히 힘들더라고요. 오랜만에 재귀를 풀어서 그런가 어떻게 해야할지는 알겠는데 막상 시도해보니 잘 안되더라고요.

아래는 코드입니다. 이런 문제를 여러개 풀어봐야하는데 언젠가 비슷한 문제가 나온다면? 꼭 30분이내로 풀어보겠읍니다.

#include<iostream>

#define MAX 51
using namespace std;

struct INFO{
	
	long long p;
	long long len;
	
};

long long n,x;
INFO hamburger[MAX];

long long eat(long long level, long long number){
	
	if(level == 0) return 1;
	if(number == 1) return 0;
	else if(number == hamburger[level - 1].len + 1) return hamburger[level - 1].p;
	else if(number < hamburger[level - 1].len + 1) return eat(level - 1, number - 1);
	else if(number == hamburger[level - 1].len + 2) return hamburger[level - 1].p + 1;
	else if(number <= hamburger[level - 1].len * 2 + 2) return hamburger[level - 1].p + 1 + eat(level - 1, number - hamburger[level - 1].len - 2);
	else return hamburger[level - 1].p * 2 + 1;
	
}

int main() {
	
	cin >> n >> x;
	
	hamburger[0] = {1,1}; // 패티 개수, 햄버거 크기 
	
	for(int i = 1; i <= n; i++){
		hamburger[i] = {hamburger[i - 1].p * 2 + 1, hamburger[i - 1].len * 2 + 3};
	}
	
	cout << eat(n,x);
	
	
	return 0;
}