[파이썬/Python] 백준 2116번: 주사위 쌓기

📌 문제 : 백준 2116번

---

📌 문제 탐색하기

n : 주사위 개수 $(1 ≤ n ≤ 10,000)$

규칙에 맞게 주사위를 쌓았을 때 4개의 긴 옆면 중 어느 한 면의 숫자 합이 최대가 되는 값을 구하는 문제이다.

문제 풀이

⭐️ 주사위 쌓는 규칙

• 위아래로 맞닿는 주사위 면의 숫자는 같아야 한다.
• 맨 밑의 주사위는 마음대로 놓을 수 있다.

주사위 숫자는 입력받은 순서대로 A, B, C, D, E, F라 했을 때,
마주 보는 숫자 짝은 다음과 같다.
{0: 5, 1: 3, 2: 4, 3: 1, 4: 2, 5: 0}

주사위가 10,000개 이하이므로 모든 주사위 배치하는 경우의 수를 구해서 그 합 중에 최댓값을 갱신해가며 구할 수 있을 것 같다.

먼저 첫번째 주사위를 놓을 수 있는 경우의 수 6가지 내에서 나머지 n개의 주사위를 놓는 경우를 고려한다.
→ 이중 for문을 이용한다.

첫번째 주사위의 옆면 중 최댓값이 합을 계산할 옆면에 있어야 하기 때문에 옆면 중 최댓값을 계산하고 누적합을 구할 변수에 더해준다.

그 다음에 쌓은 주사위도 첫번째 주사위와 동일한 값이 맞닿도록 놓고,
첫번째 주사위의 옆면 중 최댓값을 구하는 방법과 동일하게 이용한다.

이 때 주사위의 맞닿는 면에 대한 인덱스를 헷갈리지 않게 코드를 구현한다.

가능한 시간복잡도

첫번째 주사위 6면을 반복하면서 나머지 주사위까지 계산 → $O(6 * (n-1)) = O(n)$

최종 시간복잡도
$O(n)$이고 최악의 경우 $O(10000)$로 2초 내에 연산 가능하다.

알고리즘 선택

주사위를 놓을 수 있는 모든 경우의 수를 구해 최댓값 갱신해 구하기

---

📌 코드 설계하기

1. 주사위 개수 입력
2. 주사위 숫자 입력
3. 주사위 마주 보는 면 정의
4. 갱신할 최댓값 저장할 변수 정의
5. 첫번째 주사위 놓기
   5-1. 현재 합 계산
   5-2. 옆면 중 최댓값 구하기
   5-3. 옆면 중 최댓값 구하기
   5-4. 최대 합 찾기
6. 결과 출력

---

📌 시도 회차 수정 사항

1회차

• 첫번째 주사위를 제외하고 나머지 주사위의 최댓값을 구하도록 for문을 작성해야 하는데 for j in range(n):로 작성해서 첫번째 주사위부터 다시 계산하도록 코드를 작성했다.
• 두번째 주사위부터 작동하도록 수정했다.

2회차

• 계속 값이 엉뚱하게 나와서 확인해보니 각각 주사위의 인덱스에 접근해서 값을 가져올 때, 위 아래 값을 반대로 가져왔다.

---

📌 정답 코드

import sys

input = sys.stdin.readline

# 주사위 개수 입력
n = int(input())

# 주사위 숫자 입력
dices = [list(map(int, input().split())) for _ in range(n)]

# 주사위 마주 보는 면 정의
pairs = {0: 5, 1: 3, 2: 4, 3: 1, 4: 2, 5: 0}

# 갱신할 최댓값 저장할 변수 정의
max_sum = 0

# 첫번째 주사위 놓기
for i in range(6):
    up = dices[0][i]
    down = dices[0][pairs[i]]

    # 현재 합 계산
    current_sum = 0

    # 옆면 중 최댓값 구하기
    current_sum += max([num for idx, num in enumerate(dices[0]) if idx != i and idx != pairs[i]])

    for j in range(1, n):
        # 밑 주사위 숫자 = 위 주사위 숫자
        down_idx = dices[j].index(up)

        down = dices[j][down_idx]
        up = dices[j][pairs[down_idx]]

        # 옆면 중 최댓값 구하기
        current_sum += max([num for idx, num in enumerate(dices[j]) if idx != down_idx and idx != pairs[down_idx]])

    # 최대 합 찾기
    max_sum = max(max_sum, current_sum)

# 결과 출력
print(max_sum)

• 결과