BOJ 16974번: 레벨 햄버거

문제

문제 바로가기> BOJ 16974번: 레벨 햄버거

16974번: 레벨 햄버거

 

풀이

패티가 늘어나는 규칙은 " (이전 레벨 패티) * 2 + 1 " 이다.

N	0	1	2	3	4	5	...
patty	1	3	7	15	31	63	...

 

햄버거의 아래 X장을 먹는 경우에는 총 3가지 경우가 있다.

(재귀적으로, 분할정복으로 해결하기 위해)

 

1. (해당 레벨의) 가운데 패티보다 적게 먹는 경우

   : get_patty(n-1, x-1)

     = 레벨을 낮추어 재귀적으로 탐색해준다.

     x-1을 넘겨주는 이유는 앞에 햄버거 번이 하나 빠지기 때문이다.

         ex) 레벨 2 햄버거 → B BPPPB P(중간패티) BPPPB B
         X = 4 인 경우, level 1에서  X = 3과 같은 위치다. (앞에 번 하나가 빠지므로)

   

2. (해당 레벨의) 가운데 패티까지 먹는 경우

   : patty[n-1] + 1 = (가운데 패티 이전 패티 + 중간 패티)

 

3. (해당 레벨의) 가운데 패티보다 많이 먹는 경우

   : patty[n-1]+1+get_patty(n-1, x-patty[n])

     = 우선 가운데 패티까지 먹고, 레벨을 낮추어 재귀적으로 탐색해준다.

     x-patty[n]을 넘겨주는 이유는 그 만큼 먹었기 때문이다.

 

#include<iostream>
#define MAX 51
using namespace std;

int N;
long long X;
long long patty[MAX];

void make_bugger(){
    patty[0] = 1;
    for(int i=1; i<=N; i++) patty[i] = patty[i-1]*2+1;
}

long long get_patty(int n, long long x){
    if(n==0 || x==0) { // 레벨 0 버거, 다 먹은 경우
        if(x == 0) return 0; return 1;
    }
    if(patty[n] < x) return patty[n-1]+1+get_patty(n-1, x-patty[n]); // 중간 패티보다 많이 먹는 경우
    else if(patty[n] == x) return patty[n-1]+1; // 중간 패티까지 먹는 경우
    else return get_patty(n-1, x-1); // 중간 패티보다 적게 먹는 경우
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> X;
    make_bugger();
    cout << get_patty(N, X);
}