이번 문제는 백준의 골드 5 문제 레벨 햄버거이다.
문제를 차근차근 읽어보도록 하자.
최대 50까지의 햄버거 레벨이 주어진다.
각 햄버거 레벨의 구성은 번 (L-1) 패티 (L-1) 번으로 이루어진다.
예를 들어, 레벨 1의 버거는 번 L0 패티 L0 번으로 구성되는 것이다.
상근이가 아래부터 X장을 먹었을 때, 몇 장의 패티를 먹었는지 구해라!
어떻게 문제를 풀어야 할까?
분할 정복
문제를 읽었을 때 가장 먼저 떠오르는 것은 분할 정복이다.
레벨 2의 햄버거가 번 L1 패티 L1 번과 같이 구성될 것이니, 재귀적이다.
하지만 아래로부터 몇 장의 패티를 먹었는지 어떻게 계산할까?
직접 BPPPB와 같은 문자열을 재귀를 통해 만드는 것은 시간이 너무 오래걸릴 것 같다.
그도 그럴 것이 50레벨의 햄버거를 만드는 데는 너무너무 큰 수의 패티와 번이 들어간다.
아래와 같이 30레벨의 햄버거를 만드는 데에 들어가는 장 수만 이미 42억장에 달한다.
입력 및 출력해야 하는 수는 long long 타입이면 2^63 - 1이 최대이기에, 상관없을 것이다.
그 말인 즉, 어떤 수학적 계산을 통해서 빠르게 계산을 해내야 한다는 말인 것 같다.
규칙 찾기
계속 관찰하고 생각하다보니, 규칙을 만들 수 있을 것 같다.
우선 알아낼 수 있는 것은 햄버거 장수의 점화식이다.
재귀적 구성이기 때문에, (L-1) * 2 + 3장 이라는 간단한 점화식을 도출할 수 있다.
또한, 패티의 수는 매 레벨 당 (L-1) * 2 + 1장 이라는 점화식이 도출된다.
이로써 모든 단계의 총 장수, 패티 장수는 구해서 저장할 수 있게 되었다.
이제부터 패티를 먹게되는 규칙을 잘 생각해보자.
우선 당연히 1장을 먹는 경우는 레벨 0을 제외하면 모두 0이 답이다.
그럼 이제 아래와 같이 햄버거가 있을 때, 붉은 선 아래로 먹는 경우엔 어떨까?
L-1 레벨의 햄버거에서 한 번더 계산을 해야할 것 같다.
즉 재귀적으로 L-1 레벨의 햄버거로 내려가서 패티의 수를 생각한다.
그럼 처음에 입력받았던 N, X에 대해서 N-1, X-1이 되는 것이다.
X가 하나 줄어드는 이유는, 앞의 번이 하나 줄어들기 때문이다.
만약 붉은 선이 좀 더 길어져서, 한 가운데의 패티까지 먹는다면?
이 규칙은 매우 간단하게, L-1 햄버거의 패티 + 가운데 패티가 답이 된다.
붉은 선이 더더 길어져서 뒤에 나오는 L-1 햄버거 아래로 먹는 경우엔?
이 경우엔 좀 더 복잡해진다.
간단하게 생각해볼 수 있는 건, 앞의 L-1 패티와 중앙 패티 1장은 반드시 먹을 수 있다.
이제 거기에 L-1 패티에 대해서 재귀적인 계산이 들어가야 한다.
가장 처음엔 N-1, X-1이었지만, 이번엔 X-1이 아니다.
N-1은 맞지만, 먹는 장 수가 X - ((L-1 Burger) + 2)가 되어야 한다.
왜? 정 가운데의 패티까지는 이미 다 먹었다고 생각하는 것이기 때문이다!
마지막 경우인 끝까지 다먹어버리는 경우다.
이 경우엔 당연하게도, 버거에 존재하는 모든 패티를 다 먹을 수 있다.
따라서 이전에 저장해놓은 patties[N]이 된다!
최종적으로 아래와 같이 코드를 작성했다.
#define ll long long
ll burger[51], patties[51];
void pile_burger(ll num) {
burger[0] = 1; // 레벨 0 버거
patties[0] = 1; // 레벨 0 버거는 패티 뿐
for (int i = 1; i <= num; i++) {
burger[i] = burger[i - 1] * 2 + 3;
patties[i] = patties[i - 1] * 2 + 1;
// 버거는 2(n-1) + 3, 패티는 2(n-1) + 1
}
}
long long eat_burger(ll level, ll eaten) {
if (level == 0) // 레벨이 0이면 패티 1장임
return 1;
if (eaten == 1)
return 0; // 1장 먹는 경우는 반드시 0
else if (eaten <= burger[level - 1] + 1)
return eat_burger(level - 1, eaten - 1);
// 2장 ~ (번 + L - 1 길이)인 경우 N - 1, X - 1
else if (eaten == burger[level - 1] + 2)
return patties[level - 1] + 1;
// 번 + (L - 1)길이 + 패티의 경우 (L-1 패티 + 패티 1장)
else if (eaten <= burger[level - 1] * 2 + 2)
return patties[level - 1] + 1 + eat_burger(level - 1, eaten - (burger[level - 1] + 2));
// 번 + (L - 1)길이 + 패티 + (L - 1)길이의 경우 좀 복잡.
// (L-1)패티 다 먹음, 가운데 패티 먹음, 이후 (L - 1)에 대해서 재귀
// 단, 먹어야 하는 양이 (X - (이전 장수))가 되어야 하는게 핵심!
else
return patties[level];
// 남은 경우는 전체 패티를 다 먹는 경우 뿐이다.
}
int main(){
ll num = 0, eaten = 0;
cin >> num >> eaten;
pile_burger(num); // 버거를 일단 만듬
cout << eat_burger(num, eaten);
return 0;
}어렵다 어려워 DP!