백준 2116 주사위 쌓기
16 Dec 2021전형적인 DP문제. 하나씩 주사위를 쌓아가면서 가장 위의 주사위가 1~6 이 될 때 옆면의 최대 숫자를 구해주면 된다. 예를들어 가장 윗 주사위의 숫자가 3이고 반대편 주사위 숫자가 5라고 했을 때 DP[n][3] = DP[n-1][5] + PossibleSideMaxNumber[3]이 된다.
따라서 DP 공식은 다음과 같다.
DP[n][A] = DP[n-1][F] + PossibleSideMaxNumber[A]
DP[n][B] = DP[n-1][D] + PossibleSideMaxNumber[B]
// C-F 도 반복
이 때 유의할 점으로는 A-F, B-D, C-E가 짝을 이루게 되므로 어떤 숫자끼리 짝을 이루는지 미리 지정을 해주면 편하게 풀 수 있다.
- 전체 코드
import Foundation
let n = Int(readLine()!)!
var dp = Array(repeating: Array(repeating: 0, count: 7), count: n)
(0..<n).forEach { index in
let dice = readLine()!.split(separator: " ").map{ Int(String($0))! }
let pair = makePair(dice: dice)
let maxNumber = makeMaxNumber(dice: dice, pair: pair)
if index == 0 {
dp[index] = maxNumber
} else {
(0...5).forEach {
let diceNumber = dice[$0]
guard let pairNumber = pair[diceNumber] else { return }
dp[index][diceNumber] = dp[index-1][pairNumber] + maxNumber[diceNumber]
}
}
}
print(dp[n-1].max()!)
func makeMaxNumber(dice: [Int], pair: [Int: Int]) -> [Int] {
let numbers = [1, 2, 3, 4, 5, 6]
var maxNumber = Array(repeating: 0, count: 7)
(0...5).forEach {
let diceNumber = dice[$0]
guard let pairNumber = pair[diceNumber],
let tmpMaxNumber = numbers.filter({ $0 != diceNumber && $0 != pairNumber }).max()
else { return }
maxNumber[diceNumber] = tmpMaxNumber
}
return maxNumber
}
func makePair(dice: [Int]) -> Dictionary<Int, Int> {
var dict = [Int: Int]()
dict[dice[0]] = dice[5]
dict[dice[5]] = dice[0]
dict[dice[1]] = dice[3]
dict[dice[3]] = dice[1]
dict[dice[2]] = dice[4]
dict[dice[4]] = dice[2]
return dict
}