문제
문제 바로가기> BOJ 16974번: 레벨 햄버거
풀이
패티가 늘어나는 규칙은 " (이전 레벨 패티) * 2 + 1 " 이다.
N | 0 | 1 | 2 | 3 | 4 | 5 | ... |
patty | 1 | 3 | 7 | 15 | 31 | 63 | ... |
햄버거의 아래 X장을 먹는 경우에는 총 3가지 경우가 있다.
(재귀적으로, 분할정복으로 해결하기 위해)
1. (해당 레벨의) 가운데 패티보다 적게 먹는 경우
: get_patty(n-1, x-1)
= 레벨을 낮추어 재귀적으로 탐색해준다.
x-1을 넘겨주는 이유는 앞에 햄버거 번이 하나 빠지기 때문이다.
ex) 레벨 2 햄버거 → B BPPPB P(중간패티) BPPPB B
X = 4 인 경우, level 1에서 X = 3과 같은 위치다. (앞에 번 하나가 빠지므로)
2. (해당 레벨의) 가운데 패티까지 먹는 경우
: patty[n-1] + 1 = (가운데 패티 이전 패티 + 중간 패티)
3. (해당 레벨의) 가운데 패티보다 많이 먹는 경우
: patty[n-1]+1+get_patty(n-1, x-patty[n])
= 우선 가운데 패티까지 먹고, 레벨을 낮추어 재귀적으로 탐색해준다.
x-patty[n]을 넘겨주는 이유는 그 만큼 먹었기 때문이다.
#include<iostream>
#define MAX 51
using namespace std;
int N;
long long X;
long long patty[MAX];
void make_bugger(){
patty[0] = 1;
for(int i=1; i<=N; i++) patty[i] = patty[i-1]*2+1;
}
long long get_patty(int n, long long x){
if(n==0 || x==0) { // 레벨 0 버거, 다 먹은 경우
if(x == 0) return 0; return 1;
}
if(patty[n] < x) return patty[n-1]+1+get_patty(n-1, x-patty[n]); // 중간 패티보다 많이 먹는 경우
else if(patty[n] == x) return patty[n-1]+1; // 중간 패티까지 먹는 경우
else return get_patty(n-1, x-1); // 중간 패티보다 적게 먹는 경우
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> X;
make_bugger();
cout << get_patty(N, X);
}
'문제 풀이 > 백준' 카테고리의 다른 글
BOJ 2343번: 기타 레슨 (0) | 2023.02.23 |
---|---|
BOJ 6987번: 월드컵 (0) | 2023.02.22 |
BOJ 2531번: 회전초밥 (0) | 2023.02.21 |
BOJ 11053번: 가장 긴 증가하는 부분 수열 (0) | 2023.02.19 |
BOJ 2098번: 외판원 순회 (0) | 2023.02.19 |