[백준 16974] - 레벨 햄버거(C++)[실버1]

📕문제

---

상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-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 버거에 있는 레이어의 수

👀문제 해석

• 초기에는 문자열 그대로를 계속 이어붙여서 풀려고 했다.
  • 마지막 보기를 보니 이렇게 풀면 죽었다 깨어나도 제시간에 못풀거같아서 포기했다.
• 그 다음에는 일정한 규칙으로(level이 올라갈수록) 햄버거번의 수와 패티의 수가 규칙에 따라 오르는 것을 알 수 있다.
• 이러한 규칙으로 햄버거를 입력받은 level까지 만들어 놓은 다음
  햄버거를 쪼개서(분할) x장 까지의 패티의 수를 합치면 되겠다고 생각했다.

🔎문제 풀이

가정 : 햄버거번 : B , 패티 : P , N : level, X : 먹은 개수

• 우선 햄버거의 패티수와 번의 수는 이전 레벨의 햄버거에 영향을 미친다.
  • N햄버거 = B + (N-1)햄버거 + P + (N-1)햄버거 + B
  • 이러한 규칙으로 햄버거를 만들 수 있다.
• 그럼 우리는 이제 원하는 레벨에서 x장을 먹었을 때 패티를 몇장 먹었는지를 구해야 한다.
• 여기서 몇가지 경우의 수가 있습니다.
  • 우선 가장 간단한 경우의 수는  
    • 우선 x가 1이라면 무조건 빵을 먹었을겁니다. -> 패티의 수는 당연히 0이 될겁니다.
• 나머지 경우의 수는 그림으로 설명하는 것이 이해가 빠를거 같습니다.

• 1번 구간은 2가지 경우의 수가 있습니다.
  • X가 1(빵) + (N-1) 햄버거의 길이와 같을 경우 -> (N-1) 햄버거에 있는 패티의 수가 정답.
  • X가 1(빵) + (N-1)햄버거의 길이보다 작은 경우 -> 현재 햄버거를 쪼개야 합니다.
    • 그럼 우리는 그 (N-1) 햄버거에 접근을 해서 X를 -1 해줘야 합니다.(N레벨에서 빵이 하나 추가 되었기 때문입니다.)
    • 이렇게 계속 쪼갤 경우 첫 번째에 빵이 하나 추가되기에 계속 -1을 해줘야 합니다.
    • 예시를 들어 보겠습니다.
• X가 3번 구간일 때
  
  • X가 1(빵) + (N-1) 햄버거의 길이 + 1(패티)와 같은 경우 -> (N-1) 햄버거에 있는 패티의 수 + 1
• X가 2번 구간 일 때
  • (N-1) 햄버거의 패티수와 가운데 추가된 페티 수가 기본적으로 더해져야 합니다.
  • 그다음은 햄버거를 쪼개주는 작업을 합니다. [이전 레벨 햄버거로 접근하기]
    • X장을 먹었는데 이미 우리는 B+ (N-1) 햄버거 + P 작업을 처리해 줬기에,
      X = X - (N-1) 햄버거의 길이 + 2(B+P)가 될 겁니다.
• X가 4번 구간 일대
  • (N) 햄버거의 모든 패티의 수를 더해주면 됩니다.
  • (N-1) 햄버거의 패티수* 2 + 1 해주면 됩니다. 

💡예시

level 0 : P
level 1 : BPPPB
level 2 : B [BPPPB] P [BPPPB] B
만약 2,5를 입력받았다면 우리는 1번 구간이라는 것을 알 수 있습니다.
이런 경우는 햄버거의 패티 수를 이전 레벨에서 접근해야 하기에 햄버거를 쪼개줘야 합니다.
level 2에서는 5가 P였지만, level 1에서는 level2에 추가된 빵 하나가 빠지기에 5가 아닌 4로 접근을 해야 합니다.
[-1을 해주는 이유]
(2,5) ->  (1,4)가 될 겁니다. 궁극적으로 우리가 구하고 싶은 것은 패티입니다. 빵은 신경 쓸게 아니죠
BPPPB , 4 -> 2번 구간입니다.
BPP에서 패티의 수를 계산해주고 X를 4- (1(level 0 햄버거) + 2)로 바꿔줍니다.
(1,4)-> (0,1)
P에서 1장 먹었기에 우리는 추가로 1장의 패티를 얻을 수 있습니다.
따라서 level 2에서 5장을 먹었을 때 우리는 3장을 먹은 것을 알 수 있습니다.

💻코드

/*
실버1 레벨 햄버거
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long long n, x;
vector<long long> patty;
vector<long long> bread;
vector<long long> burger;
long long eat_patty(long long level, long long number);
int main()
{
    cin >> n >> x;
    patty.resize(51, 0);
    bread.resize(51, 0);
    burger.resize(51, 0);
    // 레벨 원의 햄버거는 패티로만 이루어져 있음.
    patty[0] = 1;
    bread[0] = 0;
    burger[0] = patty[0] + bread[0];
    for (int i = 1; i <= n; i++)
    {
        patty[i] = patty[i - 1] * 2 + 1; // 패티
        bread[i] = bread[i - 1] * 2 + 2; // 번
        burger[i] = patty[i] + bread[i]; // 햄버거 총 길이
    }
    cout << eat_patty(n, x);
}
long long eat_patty(long long level, long long number)
{

    if (level == 0) // 레벨이 0일 때는 패티로만 이루어져 있음.
        return 1;
    if (number == 1) // level이 0 이 아니고, 먹은 장수가 1개라면 무조건 빵이다.
        return 0;
    else if (number == burger[level - 1] + 1) // 이전 burger + 빵 한개 와 일치할때는 -> 이전 burger에 patty를 가져오면 되겟죵?
        return patty[level - 1];
    else if (number < burger[level - 1] + 1) // 이전 burger + 빵 구간일때 이전 burger구간에서 patty를 찾아야함.
        return eat_patty(level - 1, number - 1);
    else if (number == burger[level - 1] + 2) // 가운데 patty 위치일때.
        return patty[level - 1] + 1;
    else if (number <= burger[level - 1] * 2 + 2)                                           // 가운데 페티 ~ 마지막 빵 구간
        return patty[level - 1] + 1 + eat_patty(level - 1, number - burger[level - 1] - 2); // x는 이전 레벨 burger와 빵하나 패티하나를 뺴준 값이 들어가야함.
    else                                                                                    // x가 level 햄버거와 똑같을때
        return patty[level - 1] * 2 + 1;
}

✔느낀 점

• 분할정복을 사용하는 문제는 정말 까다로운 거 같다.
• 어떻게 쪼개고 나중에 쪼갠 것을 합칠 때의 코드가 거의 재귀형태로 짜이기 때문에
  재귀 함수를 잘 이해해야 한다.
• 보기에 터무니없는 값이 있어서 long long으로 짰는데 어이가 없었다.
• 지금 생각해보면 bread 벡터를 괜히 만든 건가 싶다.