Problem link
https://atcoder.jp/contests/abc115/tasks/abc115_d
Problem Summary
버거를 일정 규칙으로 쌓을 수 있다.
해당 레벨의 버거의 x층 까지 중에 패티가 몇 개인지 구하는 문제.
일정 규칙:
- 레벨 0의 버거는 패티 1개이다.
- 레벨 L의 버거는 번 + 레벨 L-1 버거 + 패티 + 레벨 L-1 버거 + 번이다.
Solution
분할 정복으로 레벨 L의 버거의 패티 수를 빨리 구할 수 있다.
번 + 레벨 L-1 버거 + 패티 + 레벨 L-1 버거 + 번
중간의 패티를 기점으로 반을 나눌 수 있고,
x가 레벨 L-1 버거의 층수 + 1 보다 작으면 레벨 L-1 버거의 패티의 개수를 구하는 식으로 재귀적으로 나눠나갈 수 있다.
대신 특정 레벨의 전체 버거 층 수 및 패티의 총 개수를 빨리 구하기 위해 먼저 전처리로 전부 구해놓았다.
Source Code
#include <iostream>
using namespace std;
long long totalLength[51];
long long pattyLength[51];
void getLength(int level) {
if (level == 0)
{
totalLength[level] = 1;
pattyLength[level] = 1;
return;
}
getLength(level - 1);
totalLength[level] = totalLength[level - 1] * 2 + 3;
pattyLength[level] = pattyLength[level - 1] * 2 + 1;
}
long long solve(int level, long long x) {
if (level == 0)
{
return 1;
}
if (x <= 1)
{
return 0;
}
else if (x <= 1 + totalLength[level - 1])
{
return solve(level - 1, x - 1);
}
else if (x == 1 + totalLength[level - 1] + 1)
{
return pattyLength[level - 1] + 1;
}
else if (x < totalLength[level])
{
return pattyLength[level - 1] + 1 + solve(level - 1, x - totalLength[level - 1] - 2);
}
else
{
return pattyLength[level];
}
}
int main() {
int n;
long long x;
cin >> n >> x;
getLength(n);
cout << solve(n, x) << endl;
}