백준 1041 주사위

출처: www.acmicpc.net/problem/1041

분류: Greedy

---

접근방식

주사위를 쌓아서 정육면체를 만들 때 각 주사위에서 서로 마주보는 면이 동시에 보일 수는 없습니다. 
따라서 마주보는 면이 안 나오게 잘 계산해서 최소값을 구해줘야 합니다.
주어진 도면에서 각 주사위의 마주보는 면은 (0, 5), (1, 4), (2, 3) 입니다.
(주사위 1개인 경우 제외)

만들어진 정육면체에서 각 주사위는 3가지 케이스 밖에 생기지 않고 각 케이스의 개수는 아래와 같습니다.

세 면이 보이는 경우 4개 ( 각 모서리 위쪽 )

두 면이 보이는 경우 4(N-1) + 4(N-2)  (옆면 모서리 + 위쪽 모서리)
한 면이 보이는 경우 4N(N-2) + (N-2)(N-2) (테두리를 제외한 옆면 + 테두리를 제외한 윗면)
마주보는 경우만 아니라면 주사위를 잘 굴려서 3가지 케이스를 만들어줄 수 있습니다.

 

각 케이스에 될 수 있는 경우의 수 중에서 최소를 찾아주면 됩니다.

세 면이 보이는 경우: 대칭이 되는 세 쌍 중에서 각각의 최소들의 합
두 면이 보이는 경우: 마주보는 면이 아닌 두 면의 합 중 최소
한 면이 보이는 경우: 주사위 6면 중 최소

 

해결방법

let n = Int(readLine()!)!
let dice = readLine()!.split(separator: " ").map{Int($0)!}
let oneFaceMin = dice.min()!
var twoFaceMin = Int.max
var threeFaceMin = Int.max

for (face, value) in dice.enumerated() {
  for secondIndex in 0...5 {
    if secondIndex == face || secondIndex == (5-face) {
      continue
    }
    for thirdIndex in 0...5 {
      if thirdIndex == face ||
        thirdIndex == 5-face ||
        secondIndex == thirdIndex ||
        secondIndex == 5-thirdIndex {
        continue
      }
      //print("threeFace: (\(face),\(secondIndex), \(thirdIndex))")
      threeFaceMin = min(value + dice[secondIndex] + dice[thirdIndex], threeFaceMin)
    }
    //print("twoFace: (\(face),\(secondIndex)")
    twoFaceMin = min(value + dice[secondIndex], twoFaceMin)
  }
}



if n == 1 {
  let diceSum = dice.reduce(0, +)
  print(diceSum - dice.max()!)
} else {
  print(threeFaceMin*4 + twoFaceMin*(n-1)*4 + twoFaceMin*(n-2)*4 + oneFaceMin*(n-1)*(n-2)*4 + oneFaceMin*(n-2)*(n-2))
}

저는 조금 복잡하게 풀었었는데 다른 분의 풀이는 보니 이렇게 간단하게 풀 수 도 있더라구요

let n = Int(readLine()!)!
let dice = readLine()!.split(separator: " ").map{Int($0)!}
let oneFaceMin = dice.min()!

var faceMin = [Int]()
faceMin.append(min(dice[0], dice[5]))
faceMin.append(min(dice[1], dice[4]))
faceMin.append(min(dice[2], dice[3]))
faceMin.sort()
let threeFaceMin = faceMin[0] + faceMin[1] + faceMin[2]
let twoFaceMin = faceMin[0] + faceMin[1]

if n == 1 {
  let diceSum = dice.reduce(0, +)
  print(diceSum - dice.max()!)
} else {
  print(threeFaceMin*4 + twoFaceMin*(n-1)*4 + twoFaceMin*(n-2)*4 + oneFaceMin*(n-1)*(n-2)*4 + oneFaceMin*(n-2)*(n-2))
}

 

배운점

 

3중 포문으로 굉장히 복잡하게 풀었었는데

다른 분들의 풀이를 보다가 모서리가 마주보는 면 중 최소들의 합이라는 사실에 무릎을 탁 쳤습니다.

화이팅