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

문제 : 16974

풀이 point

이 문제는 실제로 레벨-N 햄버거를 만들면 시간초과이다. 그렇기 때문에 P(패티)개수만 계산해야한다. 레벨 N만큼 버거 길이를 저장하는 배열과 패티 개수를 저장하는 배열이 필요하다.

풀이 방법

5가지 경우의 수가 있다.

1. x == 1일 때는(먹은 개수) return 0이다.

   먹은 패티가 없기 때문

2. x가 1 + dp[n-1]보다 작을 때 return recur(n-1, x-1)이다.

   레벨을 줄인다. 햄버거 빵은 먹은 것이기 때문에 x-1을 해준다.

3. x가 1 + dp[n-1] + 1일 때 return p[n-1] + 1

   이때가 p[n-1]일 때 구한 패티의 개수 + 1값에 해당한다.

4. x가 1 + dp[n-1] + 1 + dp[n-1] return p[n-1] + 1 + recur(n-1, x-dp[n-1]-2)

   p[n-1]일 때 구한 패티의 개수 + 1 + 길이-1, x를 먹은 만큼 없앤 값을 던져 recur을 호출한다.

5. 햄버거 번을 다 먹었을 경우 return p[n]
   길이가 n일때 먹은 패티의 개수와 같다.

코드

//백준 16974, 레벨 햄버거

#include <iostream>
using ll = long long;

ll N, X;
ll dp[51]; //버거 길이
ll p[51]; //패티 개수

ll recur(ll n, ll x){
    if(n == 0) return x;

    if(x == 1) return 0;
    else if(x <= 1 + dp[n-1]) return recur(n-1, x-1);
    else if(x == 1 + dp[n-1] + 1) return p[n-1] + 1;
    else if(x <= dp[n-1]*2 + 2) return p[n-1] + 1 + recur(n-1, x-dp[n-1]-2);
    else return p[n];
}

int main (){

    std::cin >> N >> X;

    dp[0] = 1; p[0] = 1;
    
    for(ll i{1}; i<=N; ++i){
        dp[i] = 1 + dp[i-1] + 1 + dp[i-1] + 1;
        p[i] = 2*p[i-1] + 1;
    }

    std::cout << recur(N, X);

    return 0;
}