[백준] 16974 레벨 햄버거

3 번째 예제를 보지 못하고 신나는 마음에 문제를 재귀로 쉽게 풀어내서 이게 실버문제라고..?라는 의문이 드는 순간 

무려 4천조나 되는 숫자가 나와서 매우 당황..;;

 

처음에 신나는 마음에 푼 코드.. 는 정말 단순하게 있는 그대로 구현한 것 같다.

 

끙끙 헤매다가 결국 인터넷의 힘을 빌릴 수밖에..ㅜ

 

숫자가 매우 커서 재귀를 무작정 돌리는 경우 시간초과가 나는 것은 무조건이다.

따라서 DP를 이용하여 풀어야 하는데

 

솔직히 막막하다.

 

햄버거 재료 개수랑 패티 개수를 저장할 배열을 생성한 후 미리 개수를 저장해 놓는다.

 

그리고 우리가 구하고 싶은 것은 패티! 의 개수가 중요하니까 모든 코드는 패티의 개수에 맞춰서 짠다.

 

우선 전체 코드 공개!

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)

using namespace std;

vector<long long> ham14974(51,0);
vector<long long> patty14974(51,0);

long long recursive14974(int N, long long X){
    
    if(N==0){   //레벨 0일 때
        if( X ==0 ) // 안먹은 경우
            return 0;
        else if (X == 1)    // 한 개 먹음
            return 1;
    }
    if(X==1)    // 빵 한개 먹음
        return 0;
    else if(X <= 1 + ham14974[N-1]){
        return recursive14974(N-1, X-1);    // 앞부분 빵 한개 빼야함
    }
    else if(X == 1 + ham14974[N-1] + 1){
        return patty14974[N-1] + 1;
    }
    else if(X <= 1 + ham14974[N-1] + 1 + ham14974[N-1]){
        return patty14974[N-1] + 1 +recursive14974(N-1, X - (1+ ham14974[N-1] + 1)) ;
    }
    else{
        return patty14974[N-1] + 1 + patty14974[N-1];
    }
    
}

void levelHam16974(){
    fast;
    int N;
    long long X;
    cin>>N>>X;
    
    ham14974[0] = 1;
    patty14974[0] = 1;
    for(int i=1;i<=N;++i){
        ham14974[i] = 1+ ham14974[i-1] + 1 + ham14974[i-1] + 1;
        patty14974[i] = patty14974[i-1] + 1 + patty14974[i-1];
    }
    
    cout<< recursive14974(N, X)<<"\n";
   
}

경우의 수를 나누어야 하는데

나누기 전에 알아야 하는 게 모든 레벨에서 햄버거는 가운데 패티 1개를 기준으로 좌우 대칭이 된다.

즉 가운데 추가되는 패티가 가운데인 것!

• X == 1 → 레벨이 0이 아닌 이상 빵만 먹은 것
• X <= 1 + ham14974 [N-1] → X의 크기가 중간보다 작으므로 N-1 레벨 햄버거 개수에 빵을 추가한 개수이다.
• X == 1 + ham14974 [N-1] + 1 → 중간 이전에 패티 개수, N-1 레벨 패티 개수에 중간 패티 1개를 더한 값이다.
• X <= 1 + ham14974 [N-1] + 1 + ham14974 [N-1] → 절반 이상을 먹고 다 먹기 직전의 개수
• 모두 다 먹은 경우

이렇게 총 5가지의 경우의 수로 나뉜다.

 

이런 유형 문제 암기..

 

# 참고한 블로그

1. https://100100e.tistory.com/261