[백준 16974번] 레벨 햄버거 (C++)

문제링크 : https://www.acmicpc.net/problem/16974

16974번: 레벨 햄버거

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

ll N, X;
ll burger[51], patty[51]; //버거 길이, 패티 숫자

ll func(int n, ll x) //레벨, 먹을 횟수
{
    if(n==0) return x; //패티 하나

    if(x==1) return 0; //번 확정
    else if(x <= 1 + burger[n-1]) return func(n-1, x-1); //레벨 및 1개씩 먹으며 탐색
    else if(x == 1 + burger[n-1] + 1) return patty[n-1] + 1; // 패티 1개 확정 + n-1일 때 패티 갯수
    else if(x <= 1 + burger[n-1] + 1 + burger[n-1]) return patty[n-1] + 1 + func(n-1, x-(1+burger[n-1]+1)); //앞선 경우 + burger[n-1] 경우
    else return patty[n-1] + 1 + patty[n-1]; //완성품 다먹는 경우 
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> X;

    burger[0]=patty[0]=1;

    for(int i=1; i<=N; i++)
    {
        burger[i] = 1 + burger[i-1] + 1 + burger[i-1] + 1; //번 + L-1 버거 + 패티 + L-1 버거 + 번
        patty[i] = patty[i-1] + 1 + patty[i-1]; //L-1 버거 패티 + 패티 + L-1 버거 패티
    }

    cout << func(N, X);

    return 0;
}

버거 길이와 패티 숫자를 위한 배열을 각각 선언해준다.

버거 길이의 경우 "번 + i-1 버거의 길이 + 패티 + i-1버거의 길이 + 번" 이므로 번, 패티, 번은 1로 하여 길이를 구해준다.

패티 숫자의 경우 직전 버거의 패티 + 현재 버거 패티 + 직전 버거의 패티 이므로 패티는 1로 하여 구해준다.

 

이후 경우를 나눠 패티를 계산하게 된다.

먼저 레벨이 0버거는 오직 패티밖에 없다.

따라서 추가적인 계산 없이 바로 입력받은 횟수인 x를 반환한다.

 

이후 레벨이 1이상인 경우는 다음과 같이 5가지 케이스가 존재한다.

 

먼저 먹는 횟수인 x가 1(번)인 경우는 맨 밑이 무조건 번이므로 번만 먹게 된다.

따라서 패티는 먹지 못하므로 0을 반환한다.

 

x가  1 + burger[n-1](번 + 레벨 L-1 버거)보다 작거나 같다면 맨 앞의 번을 먹고 다음 레벨의 버거를 체크하게 된다.

따라서 레벨과 먹는 횟수 둘 다 1씩 감소하며 재귀를 통해 이어서 탐색한다.

 

x가 1 + burger[n-1] + 1(번 + 레벨 L-1 버거 + 패티)와 같다면 패티를 처음에 패티 숫자를 담은 배열을 통해 구할 수 있다.

맨 처음 1인 번이므로 논외, burger[n-1]에 대한 패티수는 patty[n-1], 뒤에 1은 패티이다.

따라서 patty[n-1]+1인 것을 알 수 있다.

 

x가 1 + burger[n-1] + 1 + burger[n-1](번 + 레벨 L-1 버거 + 패티 + 레벨 L-1 버거)보다 작거나 같다면 우선 앞에 부분 (1 + burger[n-1] + 1) 에 대해서 이미 계산을 했었으므로 이를 참고할 수 있다.

그러면 남은 것은 burger[n-1]인데 이는 x가  1 + burger[n-1]보다 작거나 같은 경우를 참고하여 해결할 수 있다.

이때는 앞에 빵을 먹어 1개를 제거하고 넘겨줬으나, 이 경우는 1 + burger[n-1] + 1에 대해 계산을 했으므로 현재 x에 1 + burger[n-1] + 1만큼을 빼주고 이 값을 재귀로 넘겨줘야 한다.

따라서 patty[n-1] + func(레벨 1 감소, x - ( 1 + burger[n-1] + 1))인 것을 알 수 있다.

 

마지막으로 1 + burger[n-1] + 1 + burger[n-1] + 1 즉, 완성품을 모두 먹는 경우이다.

해당 경우도 앞서 사용했던 방법을 참고하여 쉽게 해결이 가능하다.

1(번) + burger[n-1]의 경우 patty[n-1]개의 패티를 가졌고 이런 케이스가 2가지 이므로 2번 더해준다.

그리고 가운데 패티의 경우 따로 1개를 더하며 결과적으로 patty[n-1] + 1 + patty[n-1]을 해주면 된다.

 

레벨이 클수록 재귀를 통해 버거의 패티수가 매우 크게 증가하므로 (예제 50 4321098765432109 참고) 관련된 값들을 long long으로 선언해주어야 한다.