[G5] 백준 16974번 레벨 햄버거 C++ 다이나믹 프로그래밍, 재귀, 분할 정복

리뷰

 

https://www.acmicpc.net/problem/16974

완전 직관적인 문제

 

 

전역 변수

• s : 햄버거의 레벨 당 전체 크기를 저장할 배열
• p : 햄버거의 레벨 당 패티 개수를 저장할 배열

 

함수

1. eat

ll eat(int level, ll x) {
    if (x <= 0) return 0;
    if (level == 0) return 1;

    if (x == 1) return 0;

    if (x <= 1 + s[level - 1]) {
        return eat(level - 1, x - 1);
    }

    if (x == 1 + s[level - 1] + 1) {
        return p[level - 1] + 1;
    }

    if (x <= 1 + s[level - 1] + 1 + s[level - 1]) {
        return p[level - 1] + 1 + eat(level - 1, x - (1 + s[level - 1] + 1));
    }

    return p[level];
}

 

햄버거를 먹는 시뮬레이션을 진행할 함수

 

 

문제풀이

1. n, x값을 입력 받고, s[0]와 p[0]을 모두 1로 초기화한다.
2. 1~n까지 for문을 순회하며 s[i]는 s[i - 1] * 2 + 3, p[i]는 s[i - 1] * 2 + 1로 저장한다.
3. eat함수에 n, x값을 매개변수로 전달하여 호출한다.
4. eat함수 내부에선 변수 level, x에 매개변수를 파싱하여 저장한다.
5. x가 0이하면 더 먹을 것이 없기 때문에 0을 리턴한다.
6. level이 0이면 패티 한장만 남은 상태이기 때문에 1을 리턴한다.
7. x가 1이면 먹을 수 있는게 번 밖에 없기 때문에 0을 리턴한다.
8. x가 1+s[level-1]이하라면 번 하나를 먹고 나온 이전레벨의 햄버거밖에 없기 때문에 eat(level-1, x-1)을 호출하고, 결과값을 리턴한다.
9. x가 1+s[level-1]+1이라면 번 하나 + 이전레벨 햄버거 하나 + 패티 하나를 먹었기 때문에 p[level-1]+1을 리턴한다.
10. x가 1+s[level-1]+1+s[level-1]이하일 경우 번 하나 + 이전레벨 햄버거 하나 + 패티 하나 + 이전레벨 햄버거를 먹는 중이기 대문에 p[level-1]+1+eat(level01, x-(1+s[level-1]+1)을 호출하고 결과값을 리턴한다.
11. 위 조건에 모두 해당하지 않는다면 현재 레벨 햄버거를 모두 먹을 수 있는 것이기 때문에 p[level]을 리턴한다.
12. eat함수의 최종 리턴값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. DP로 버거의 전체 크기와 패티의 개수를 구해준 후 재귀를 통해 답을 빠르게 구할 수 있다.
2. 어차피 버거는 팰린드롬 형태이기 때문에 위에서 먹던 아래서 먹던 상관이 없다.

 

정답 코드

#include<iostream>
using namespace std;
using ll = long long;

ll s[51], p[51];

ll eat(int level, ll x) {
    if (x <= 0) return 0;
    if (level == 0) return 1;

    if (x == 1) return 0;

    if (x <= 1 + s[level - 1]) {
        return eat(level - 1, x - 1);
    }

    if (x == 1 + s[level - 1] + 1) {
        return p[level - 1] + 1;
    }

    if (x <= 1 + s[level - 1] + 1 + s[level - 1]) {
        return p[level - 1] + 1 + eat(level - 1, x - (1 + s[level - 1] + 1));
    }

    return p[level];
}

int main() {
    int n;
    ll x;
    cin >> n >> x;

    s[0] = 1;
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] * 2 + 3;
        p[i] = p[i - 1] * 2 + 1;
    }

    cout << eat(n, x);
}