백준 16974 레벨 햄버거

문제 설명

• 레벨 L버거는 다음과 같이 만든다
  • 레벨-0 버거는 패티만으로 이루어져 있다.
  • 레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, 패티, 레벨-(L-1)버거, 햄버거번으로 이루어져 있다. (L ≥ 1)
• 상도가 상근날드에 방문해서 레벨-N 버거를 시켜서 햄버거의 아래 X장을 먹었을 때, 먹은 패티는 몇 장일까?

문제 링크

문제 접근

1. 모든 문자열을 다 재귀를 통해 구해서 패티의 개수를 세면 문자열의 크기가 2^50을 넘어가서 한번 순회하는 O(n)로직으로도 시간초과가 난다는 것을 파악 후 다른 방식으로 생각을 했다.
2. 분할 정복을 풀어본 적은 없지만 왠지 분할정복 알고리즘 일 것 같아서 급하게 공부를 했다.
   • 분할정복은 재귀를 사용하지만, 모든 부분을 재귀를 사용하는 것이 아닌, 중복되는 부분은 간단한 연산을 통해 재귀의 횟수를 줄이는 알고리즘으로 이해했다.
3. 이후 가벼운 DP를 섞어서 문제풀이를 성공했다.

문제 풀이 코드

#include <iostream>

using namespace std;

long    len[51];
long    mac[51];

long    sol(long N, long X)
{
    long ret = 0;

    if (X < 1)
        return (0);
    if (N == 0)
        return (1);
    if (X - 1 < len[N - 1]) // 내 길이의 반보다 작은 경우
        return (sol(N - 1, X - 1));
    else if (X >= len[N]) // 딱 내 길이인 경우
        return (mac[N]);
    else if (X  - 1 == len[N - 1]) // 딱 내 길이의 절반인 경우
        return (mac[N - 1]);
    else // 내 길이의 반보다 큰 경우
        return (mac[N - 1] + 1 + sol(N - 1, X - len[N - 1] - 2));
}

int main()
{
    long    N, X;
    long ret = 0;

    len[0] = 1;    len[1] = 5;    mac[0] = 1;    mac[1] = 3;
    for (int i = 2; i < 51; i++)
    {
        len[i] = len[i - 1] * 2 + 3;
        mac[i] = mac[i - 1] * 2 + 1;
    }
    cin>>N>>X;
    ret = sol(N, X);
    cout<<ret<<endl;
}