[swift] 백준 : 16974번: 레벨 햄버거

문제 링크

16974번: 레벨 햄버거

---

문제

상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-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 버거에 있는 레이어의 수

예제

---

성공 풀이

let NX = readLine()!.split { $0 == " " }.map { Int($0)! }
let N = NX[0], X = NX[1]
var total = [1]+Array(repeating: 0, count: 50)
var patty = [1]+Array(repeating: 0, count: 50)

for i in 1...N {
    total[i] = total[i-1]*2+3
    patty[i] = patty[i-1]*2+1
}

func sol(n: Int, x: Int) -> Int {
    if n == 0 { return x }
    if x == 1 { return 0 }
    if x == total[n] { return patty[n] }
    
    if x == total[n-1] + 2 {
        return patty[n-1] + 1
    } else if x < total[n-1] + 2 {
        return sol(n: n-1, x: x-1)
    } else {
        return patty[n-1] + 1 + sol(n: n-1, x: x - (total[n-1] + 2))
    }
}

print(sol(n: N, x: X))