문제
상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-L 버거이다. 레벨-L 버거는 다음과 같이 만든다.
- 레벨-0 버거는 패티만으로 이루어져 있다.
- 레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, 패티, 레벨-(L-1)버거, 햄버거번으로 이루어져 있다. (L ≥ 1)
예를 들어, 레벨-1 버거는 'BPPPB', 레벨-2 버거는 'BBPPPBPBPPPBB'와 같이 생겼다. (B는 햄버거번, P는 패티)
상도가 상근날드에 방문해서 레벨-N 버거를 시켰다. 상도가 햄버거의 아래 X장을 먹었을 때, 먹은 패티는 몇 장일까? 한 장은 햄버거번 또는 패티 한 장이다.
입력
첫째 줄에 N과 X가 주어진다.
출력
첫째 줄에 상도가 먹은 패티의 수를 출력한다.
제한
- 1 ≤ N ≤ 50
- 1 ≤ X ≤ 레벨-N 버거에 있는 레이어의 수
예제 입력 1
2 7
예제 출력 1
4
예제 입력 2
1 1
예제 출력 2
0
예제 입력 3
50 4321098765432109
예제 출력 3
2160549382716056
문제 해결 과정
사실 문제만 읽고는 너무 쉽게 풀거라고 생각했다.
레벨-L버거를 만드는 함수는 나에게도 쉽게 만들 수 있을 것이라 생각했기 때문이다.(사실 나는 재귀 함수, 분할 정복 이런 문제를 잘 못 푼다.)
일단 그래서 레벨-L 버거를 만드는 로직을 DP를 써서 만들었다.
N, X = map(int, input().split())
list = ['P']
for i in range(1, N+1) :
burger = 'B' + list[i-1] + 'P' + list[i-1] + 'B'
list.append(burger)
cnt = 0 이러고 사실 P의 개수를 세면 될 거라고 생각을 했지만 숫자가 점점 커진다는 것을 간과하고 있었다. 당연히 메모리 초과도 떴다.
그러면 패티 개수와 전체 개수(빵과 패티)를 이용해서 해결을 해야겠다는 생각을 했다. 사실 여기서 나는 더 진행하지 못하고 블로그를 참고 했다.
일단 버거의 레이아웃 개수와 버거의 패티 개수를 DP를 활용해 담아 두고 체크를 해야했다.
4가지의 케이스로 나눌 수 있는데 다음과 같다.
(X값 기준들)
첫 번째 케이스는 중간 패티 전까지만 먹을 때다.
이러면 재귀 함수를 사용해 전 레이어 단계, 그리고 X-1 값을 이용해서 돌릴 수 있다.
두 번째 케이스는 딱 중간 패티까지 먹을 때다.
이때는 전 레이어 단계의 패티 개수와 중간 패티 하나를 합해 리턴할 수 있다.
세 번째 케이스는 중간 패티 다음부터 마지막 빵 전까지 먹을 때다.
이때는 두 번째 케이스까지의 패티 개수와 재귀 함수를 사용해 전 레이어 단계와 X에서 이전 단계의 레이어 개수와 2를 빼서 돌린다.
마지막으로는 끝까지 다 먹었을 때라 이번 레이어 단계의 패티 개수를 리턴하면 된다.
최종 코드
N, X = map(int, input().split())
burger = [1] * 51
patty = [1] * 51
for i in range(1, N+1):
burger[i] = 1 + burger[i-1] + 1 + burger[i-1] + 1
patty[i] = patty[i-1] + 1 + patty[i-1]
def eat(n, x):
if n == 0:
return x
if x == 1:
return 0
elif x <= 1 + burger[n-1]: # case 1
return eat(n-1, x-1)
elif x == 1 + burger[n-1] + 1: # case 2
return patty[n-1] + 1
elif x <= burger[n-1] + burger[n-1] + 1 + 1: # case 3
return patty[n-1] + 1 + eat(n-1, (x-(burger[n-1]+2)))
else: # case 4
return patty[n]
print(eat(N, X))참고 블로그
