[99클럽 코테 스터디 25일차 TIL] 주사위 쌓기 - 백준 2116

오늘도 완전탐색 문제이다.

 

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

천수는 여러 종류의 주사위를 가지고 쌓기 놀이를 하고 있다. 
주사위의 모양은 모두 크기가 같은 정육면체이며 각 면에는 1부터 6까지의 숫자가 하나씩 적혀있다. 
그러나 보통 주사위처럼 마주 보는 면에 적혀진 숫자의 합이 반드시 7이 되는 것은 아니다.
주사위 쌓기 놀이는 아래에서부터 1번 주사위, 2번 주사위, 3번 주사위, … 의 순서로 쌓는 것이다. 

쌓을 때 다음과 같은 규칙을 지켜야 한다.
- 서로 붙어 있는 두 개의 주사위에서 아래에 있는 주사위의 윗면에 적혀있는 숫자는 위에 있는 주사위의 아랫면에 적혀있는 숫자와 같아야 한다. 
  다시 말해서, 1번 주사위 윗면의 숫자는 2번 주사위 아랫면의 숫자와 같고, 
  2번 주사위 윗면의 숫자는 3번 주사위 아랫면의 숫자와 같아야 한다. 
- 단, 1번 주사위는 마음대로 놓을 수 있다.

이렇게 쌓아 놓으면 긴 사각 기둥이 된다. 이 사각 기둥에는 4개의 긴 옆면이 있다. 
이 4개의 옆면 중에서 어느 한 면의 숫자의 합이 최대가 되도록 주사위를 쌓고자 한다. 
이렇게 하기 위하여 각 주사위를 위 아래를 고정한 채 옆으로 90도, 180도, 또는 270도 돌릴 수 있다. 
한 옆면의 숫자의 합의 최댓값을 구하는 프로그램을 작성하시오.

[입력]
첫줄에는 주사위의 개수가 입력된다. 
그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 
주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 주사위의 전개도에서 A, B, C, D, E, F 의 순서로 입력된다. 
입력되는 숫자 사이에는 빈 칸이 하나씩 있다. 
주사위의 개수는 10,000개 이하이며 종류가 같은 주사위도 있을 수 있다.

[출력]
첫줄에 한 옆면의 숫자의 합이 가장 큰 값을 출력한다.

출처: https://www.acmicpc.net/problem/2116

풀이 접근

2번째 주사위부터는 올리고 싶은대로 놓는게 아니라

이전 주사위의 윗면에 의존되기 때문에 각 인덱스에 해당하는 반대편 인덱스를 빠르게 찾기위해 Dictionary로 정의했다.

let opposite: [Int:Int] = [
    0:5, 1:3, 2:4,
    5:0, 3:1, 4:2
]

 

각 층의 주사위를 돌려가면서 값을 구하는게 아니라 최대값을 구하는 것이기 때문에

윗면과 아랫면에 따라 4,5,6 중 하나라고 생각했다.

 

예를 들면 다음과 같다.

윗면 혹은 아랫면이 6이면서
-> 반대편 숫자가 5라면 -> 나머지 숫자 중 최댓값 4
-> 반대편 숫자가 5가 아니라면 -> 나머지 숫자 중 최댓값 5

조건에 따라 윗면과 아랫면이 같은 상황은 없기에 다음과 같이 조건식을 만들 수 있다.

if (윗면 == 6 && 아랫면 == 5) || (윗면 == 5 && 아랫면 == 6) {
    해당 층의 최댓값 = 4
} else if 윗면 == 6 || 아랫면 == 6 {
    해당 층의 최댓값 = 5
}

이 외에는 최대값이 항상 6일 것이기 때문에

전체 층 * 6에 각 층마다 최대값이 4일 때는 -2, 5일 때는 -1을 해주면된다고 생각했다.

각 층을 돌면서 6에서 빼야하는 숫자를 최소로하는 값이 전체 합을 최대로 만들어주는 것이다.

그리고 층을 돌다가 이미 이전 값보다 4 혹은 5의 값이 많아지는 경우에는 나머지 층을 볼 필요가 없기 때문에 break 조건도 만들어준다.

var result = 10_001
for i in 1..<7 {
    var prev = i
    var temp = 0
    for d in dices {
        let next = d[opposite[d.firstIndex(of: prev)!]!]
        if (prev == 6 && next == 5) || (prev == 5 && next == 6) {
            temp += 2
        } else if prev == 6 || next == 6 {
            temp += 1
        }
        prev = next
        if temp > result + 2 { break }
    }
    result = min(temp, result)
    if result == 0 { break }
}

 

마지막으로 주사위가 하나뿐일때는 예외적으로 그냥 n * 6이다.

print((6 * n) - (n <= 1 ? 0 : result))

최종 코드 - Swift

let n = Int(readLine()!)!
var dices: [[Int]] = []
let opposite: [Int:Int] = [
    0:5, 1:3, 2:4,
    5:0, 3:1, 4:2
]
(0..<n).forEach { i in
    dices.append(readLine()!.split(separator: " ").map { Int("\($0)")! })
}
var result = 10_001
for i in 1..<7 {
    var prev = i
    var temp = 0
    for d in dices {
        let next = d[opposite[d.firstIndex(of: prev)!]!]
        if (prev == 6 && next == 5) || (prev == 5 && next == 6) {
            temp += 2
        } else if prev == 6 || next == 6 {
            temp += 1
        }
        prev = next
        if temp > result + 2 { break }
    }
    result = min(temp, result)
    if result == 0 { break }
}
print((6 * n) - (n <= 1 ? 0 : result))

최종 코드 - Python3

n = int(input())
opposite = {
    0:5, 1:3, 2:4,
    5:0, 3:1, 4:2
}
dices = [list(map(int,input().split())) for _ in range(n)]
result = 10001
for i in range(1,7):
    prev = i
    temp = 0
    for d in dices:
        next = d[opposite[d.index(prev)]]
        if (prev == 6 and next == 5) or (prev == 5 and next == 6):
            temp += 2
        elif prev == 6 or next == 6:
            temp += 1
        prev = next
        if temp > result + 2: break
    result = min(temp, result)
    if result == 0: break
print((6 * n) - (0 if n <= 1 else result))

Conclusion

권장 시간이 1시간30분인데 1시간정도 걸렸다.
조건문을 작성에서 시간을 너무 낭비했다.