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

문제 링크

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

---

◆문제 해결 및 설명◆

 

알고리즘 분류 : 다이나믹 프로그래밍, 분할 정복, 재귀

 

간단하게 문제를 풀이하자면 N 레벨 햄버거 내부는

{Bun (N-1레벨 햄버거) Petty (N-1레벨 햄버거) Bun} 로 이루어져 있을 때,

뒤에서 M장을 먹었을 때 패티의 갯수를 구하는 문제이다.

 

N 레벨의 버거의 길이 공식은 N : (N-1) *2 + 3 이므로 대략 2의50승을 넘어갈 것이므로 이를 직접 뒤에서 지우며 실행할 수 는 없고, 동적 프로그래밍의 힘을 써야 한다. 아래는 4레벨 까지의 버거 내용이다. (레벨1의 버거는 띄어쓰기를 하지 않았다.)(P 와 B는 추가된 번과 패티이다.

 

0 : P
1 : BPPPB
2 : B BPPPB P BPPPB B
3 : B B BPPPB P BPPPB B P B BPPPB P BPPPB B B
4 : B B B BPPPB P BPPPB B P B BPPPB P BPPPB B B P B B BPPPB P BPPPB B P B BPPPB P BPPPB B B B

 

여기서 찾을 수 있는 특징은 

1. 뒤에있는 패티를 전부 치우면 레벨2 버거가 나온다.

즉 아랫단계의 버거를 내부에서 찾을 수 있다. 

4 : (생략) P B B BPPPB P BPPPB B P B BPPPB P BPPPB B B B (레벨1)

이를 응용하여 레벨 1 버거가 아닌 더 높은 버거도 찾을 수 있다.

4 : (생략) P B B BPPPB P BPPPB B P B BPPPB P BPPPB B B B (레벨2)

∴ (먹어야 하는 번의 갯수) = (현재 버거의 레벨) - (찾을 버거의 레벨)

---

2. N-1 버거 만큼과 P 그리고 B를 먹으면 다시 N-1 버거와 B하나가 남는다는 것이다.

4 : B B B BPPPB P BPPPB B P B BPPPB P BPPPB B B (생략) (레벨3)

---

3. 패티의 개수는 N : (N-1 버거 패티 수) * 2 + 1 , 전체 길이는 N : (N-1) *2 + 3가 된다.

이를 통해 버거의 길이와 패티수를 다이나믹 프로그래밍으로 구현하는 것이 가능하다.

#include <iostream>
#include <vector>
std::vector<std::pair<int64_t, int64_t>> dp(52); // petty,len

	dp[0] = std::make_pair(1, 1);
    for (int i = 1; i <= level + 1; i++)
    {
        dp[i] = std::make_pair(dp[i - 1].first * 2 + 3, dp[i - 1].second * 2 + 1);
        // std::cout << i << " : " << dp[i].first << "," << dp[i].second << std::endl;
    }

---

입력에는 (레벨-N 버거), (먹은 아래 M장)이 주어지고 이를 함수를 통해 재귀적으로 풀었다.

함수의 매개변수는 (버거의 레벨), (먹을 수 있는 가장 큰 버거) 이다.

 

함수를 통해

1. 먹을 양 == 먹을 수 있는 가장 큰 레벨 버거 + 뒤에있는 번

2. 먹을 게 (버거 + 번) 보다 많다면 이후 패티를 먹는다.

3. 먹을게 (버거 + 번) 보다 적다면, 뒤에 있는 번만 먹는다.

로 나누어서 구현하였다. 

 

◆코드 전문◆

#include <iostream>
#include <vector>
#include <string>
std::vector<std::pair<int64_t, int64_t>> dp(52); // petty,len
int64_t eat, answer = 0;

int eati(int level, int cnt)
{
    // eat == cnt 레벨 버거 + 뒤에있는 번
    if (eat == dp[cnt].first + (level - cnt))
    {
        answer += dp[cnt].second;
        eat -= dp[cnt].first;
        eat -= (level - cnt);
    }
    // 먹을 게 (버거 + 번) 보다 많다면 이후 패티를 먹는다.
    else if (eat > dp[cnt].first + (level - cnt))
    {
        eat -= (level - cnt);
        answer += dp[cnt].second;
        eat -= dp[cnt].first;
        eat--;
        answer++;
    }
    // 먹을게 (버거 + 번) 보다 적다면, 뒤에 있는 번만 먹는다.
    else if (eat < dp[cnt].first + (level - cnt))
    {
        eat -= (level - cnt);
    }

    if (eat <= 0)
    {
        return 0;
    }

    level = cnt;
    for (int i = 0; eat >= dp[i].first; i++)
    {
        level = i;
    }
    eati(cnt, level);
    return 0;
}

int main()
{
    int level;
    std::cin >> level >> eat;
    int cnt = level;

    dp[0] = std::make_pair(1, 1);
    for (int i = 1; i <= level + 1; i++)
    {
        dp[i] = std::make_pair(dp[i - 1].first * 2 + 3, dp[i - 1].second * 2 + 1);
    }
    if (eat == dp[level].first)
    {
        std::cout << dp[level].second;
        return 0;
    }
    //(먹을 수 있는 가장 큰 버거) 값을 찾는다. (cnt에 저장)
    for (int i = 0; eat >= dp[i].first; i++)
    {
        cnt = i;
    }

    eati(level, cnt);
    std::cout << answer;
}