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

 

https://www.acmicpc.net/problem/16974

16974번: 레벨 햄버거

 

골머리 썩혔던 문제..^^

처음에는 문제를 DP로 문자열을 계속 추가해서 진행했는데, 마지막 예제 입력인 

50 4321098765432109

여기서 출력 값이 도저히 안 나와서 이렇게 하면 안 되는구나 싶었다.

N이 50보다 작거나 같은 값이길래 될 줄 알았지.. X값이 저럴 줄이야...

 

사실 어떻게 하면 좋을지 모르겠어서 구글링을 해봤다. 다른 사람들은 어떻게 했는지 확인하기 위해...!!

 

https://nim-code.tistory.com/268

(c++)백준 16974번: 레벨 햄버거

 

이 분을 코드를 보게 되었는데, 재귀함수를 사용해서 이전 레벨 햄버거에 가서 패티 개수를 구하는 것이었다..!!

일단 어떤 식으로 풀었는지만 확인하고 혼자 구현해보려고 노력했다...ㅠ

 

- ingredient[i]: 레벨 i 햄버거를 구성하는 전체 재료 개수

- patty[i]: 레벨 i 햄버거를 구성하는 패티 개수

 

위의 값을 DP로 n번째 햄버거까지 쭉 만들어준다.

 

이제부터 재귀함수가 들어간다... 재귀 함수 머리 아파~

나는 3가지 경우의 수로 나눴다. (+1)

레벨 N버거: 빵 + 레벨 N-1 버거 + 패티 + 레벨 N-1 버거 + 빵

1. 빵 + 레벨N-1버거 + 패티까지 먹은 경우

2. 빵 + 레벨N-1버거 범위 내, x개의 재료를 먹은 경우

3. 빵 + 레벨N-1버거 + 패티를 먹고 더 먹은 경우

+ 햄버거 다 먹은 경우 -> x == ingredient[n] -> patty[n] 출력

 

그전에, 빼줄 애들은 빼줘야 한다.

1. n == 0 : 레벨 0 버거 (패티 1개뿐)

    -> x == 1: 1 나머지는 0

2. x == 1 : 맨 처음은 빵뿐이므로 return 0

 

이제 경우의 수에서 더 들어가 보자!

1. 빵 + 레벨 N-1 버거 + 패티까지 먹은 경우

    이 경우, 패티 한 장  + 레벨 N-1 버거의 패티 개수(patty[n-1])를 출력하면 끝!

 

2. 빵 + 레벨N-1버거 범위 내, x개의 재료를 먹은 경우

    이 경우, 중앙에 있는 패티 한 장은 먹지 않은 것이다. 즉, 레벨 N-1 버거 내에서 패티를 몇 개 먹었는지 알아내야 한다.

    우리는 레벨 0~N버거의 패티의 개수가 몇 개인지만 알고 있기 때문에 레벨 N-1 버거로 들어가서 다시 진행해줘야 한다.

    그러므로 return countPatty[n: n-1, x: -1]

    여기서 x는 (빵 + 레벨 N-1 버거) 여기에서 앞에 빵을 빼준 것이다!

 

3. 빵 + 레벨N-1버거 + 패티를 먹고 더 먹은 경우

    이 경우, 이미 1번의 경우의 재료는 다 먹은 것이다. 그다음의 패티를 몇 개 먹었는지를 알아야 한다.

    그러므로 return (patty[n-1] + 1(1번에서 먹은 패티 개수)) + countPatty[n: n-1, x: x - (2 + ingredient[n-1])]

    여기서 x는 앞에서 먹은 애들 빼준 것이다. (빵 + 레벨 N-1 재료 + 패티)

 

 

모르겠다면,,, n:2인 경우로 하나하나 해보세요^^!

 

import Foundation

/*
 레벨-0 버거: 패티만
 레벨-L 버거: 햄버거번, 레벨L-1버거, 패티, 레벨L-1버거, 햄버거번
 예) 레벨-1버거: BPPPB (햄버거번, 레벨L0버거, 패티, 레벨L0버거, 햄버거번)
    레벨-2버거: BBPPPBPBPPPBB (햄버거번, 레벨1버거, 패티, 레벨1버거, 햄버거번)
 레벨N버거를 시켰다. 아래서부터 X장을 먹었을 때, 먹은 패티는 몇 장?
 */

let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
let n = input[0]
let x = Int64(input[1])
var answer : Int64 = 0
var ingredient = [Int64](repeating: 0, count: 51)
var patty = [Int64](repeating: 0, count: 51)
ingredient[0] = 1
patty[0] = 1
for i in 1...n {
    ingredient[i] = 3 + ingredient[i-1] * 2
    patty[i] = 1 + patty[i-1] * 2
}

func countPatty(n: Int, x: Int64) -> Int64 {
    guard n != 0 else { //Level0버거
        return x == 1 ? 1 : 0
    }
    guard x != 1 else { //맨 처음은 빵
        return 0
    }
    guard x != ingredient[n] else {
        return patty[n]
    }
    
    if x == 2 + ingredient[n - 1] {
        return patty[n - 1] + 1
    }else if x <= 1 + ingredient[n - 1] {
        return countPatty(n: n - 1, x: x - 1)
    }else if x > 2 + ingredient[n - 1] {
        //이미 먹은 (빵 + level-1버거 + 패티) + 다음 부분
        return patty[n - 1] + 1 + countPatty(n: n - 1, x: x - (2 + ingredient[n - 1]))
    }
    return 0
}
print(countPatty(n: n, x: x))

 

 

 

보이시나요 저의 노력이...

꼭 풀고 싶었다... 흑흑

 

재귀 문제를 많이 풀어봐야겠다!