[알고리즘|파이썬] 백준 2116 주사위 쌓기
문제 링크: https://www.acmicpc.net/problem/2116
📌 문제 탐색하기
시간 제한: 2초
메모리 제한: 128 MB
✏️ 구해야 하는 정답
문제
- 1~6 숫자가 모든 면에 적혀 있음
- 마주보는 면 숫자의 합이 7은 아님
- 서로 붙어 있는 두 개의 주사위에서 [아래에 있는 주사위의 윗면에 적혀있는 숫자]는 [위에 있는 주사위의 아랫면에 적혀있는 숫자]와 같아야 함
- 4개의 옆면 중에서 어느 한 면의 숫자의 합이 최대가 되도록 주사위를 쌓고자 함
- 각 주사위를 위 아래를 고정한 채 옆으로 90도, 180도, 또는 270도 돌릴 수 있음
조건
- 1 ≤ n ≤ 10,000
- 종류 같은 주사위 있을 수 있음
📌 풀이하기
이 문제는 주사위를 쌓을 때 옆면 숫자의 합이 최대가 되는 경우를 찾는 문제다.
우리는 다음과 같은 접근 방식으로 문제를 해결한다.
1️⃣ 첫 번째 주사위의 모든 경우의 수 고려
• 주사위의 어느 면이 아랫면이 되느냐에 따라 전체 쌓기 방식이 달라진다.
• 따라서 첫 번째 주사위에서 가능한 6가지 아랫면 선택을 모두 탐색한다.
2️⃣ 각 경우에 대해 옆면 숫자의 합 계산
• 주사위를 쌓을 때, 윗면과 아랫면을 제외한 나머지 4개의 숫자 중 최댓값을 선택하여 합산한다.
• 첫 번째 주사위에서 아랫면을 고정한 뒤, 윗면 값을 찾아서 다음 주사위와 연결한다.
3️⃣ 윗면과 아랫면 연결
• 아랫면을 i라고 하면, 윗면은 find_opposite(i)를 이용해 찾는다.
• 이후, 윗면 값을 다음 주사위의 아랫면으로 지정하여 반복적으로 탐색한다.
4️⃣ 최댓값 갱신
• 모든 경우를 탐색하며, 최댓값을 max_sum에 저장한다.
📌 코드 설계하기
1. 주사위 개수 n과 각 주사위 A~F 값 입력
2. 최대 옆면 숫자 합 max = 0 으로 초기화
3. 1번 주사위에서 가능한 모든 경우의 수 탐색
4. 1번 주사위의 top 이 2번 주사위의 bottom이 되도록, 2번 주사위의 top이 3번 주사위의 bottom 이 되도록 .. 을 반복하며 쌓기
5. 한 경우에 대해 옆면의 최댓값 합 구하기
6. 모든 경우 중 최댓값 구하여 출력
📌 정답 코드
n = int(input())
dices = [list(map(int, input().split())) for _ in range(n)]
def find_opposite(i):
return [5, 3, 4, 1, 2, 0][i]
max_sum = 0
for i in range(6):
bottom = dices[0][i]
top = dices[0][find_opposite(i)]
tmp_sum = 0
tmp_sum += max([d for j, d in enumerate(dices[0]) if j not in (i, find_opposite(i))])
next_top = top
for j in range(1, n):
idx = dices[j].index(next_top)
next_top = dices[j][find_opposite(idx)]
tmp_sum += max([d for k, d in enumerate(dices[j]) if k not in (idx, find_opposite(idx))])
max_sum = max(max_sum, tmp_sum)
print(max_sum)