99클럽 코테 스터디 25일차 TIL / 완전탐색

✏️ 문제

[백준/BOJ] 2116번: 주사위 쌓기(https://www.acmicpc.net/problem/2116)

 

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

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

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

 

🤖 입출력 예시

 

🧐 난이도/소요 시간

✅ 난이도: solved.ac 기준 G5

✅ 소요 시간: 1시간 30분 초과

✅ 권장 시간: 1시간 30분

 

💡 풀이

1) 문제 이해

여러 개의 주사위를 쌓아서 옆면에 적힌 숫자의 합 중 최댓값을 구하는 문제다. 네 옆면의 합을 다 구할 필요는 없고 네 면 중 가장 큰 값을 기준으로 매 주사위마다 옆면 중 최댓값을 누적으로 더해주면 된다.

 

문제에서 '1번 주사위는 마음대로 놓을 수 있다'는 조건을 줬는데 이걸 잘 활용해야 한다.

 

2) 아이디어 흐름 및 코드

① 짝 인덱스 리스트 정의

pair_idx = [5, 3, 4, 1, 2, 0]

 

• 주사위를 이루는 값이 입력되는 순서는 전개도를 기준으로 A, B, C, D, E, F이고 각 면은 A-F / B-D / C-E로 짝지어진다. 
• A~F에 해당하는 값의 인덱스는 0~5이다.
• pair_idx[i] = i번째 면과 마주보는 면
  • i=0은 A면을 의미하고 pair_idx[0]은 A면과 마주보는 F면의 인덱스 값이다.

 

② 1번 주사위 배치하기

for i in range(6):
    top, bottom = dice_list[0][pair_idx[i]], dice_list[0][i]
    
    # 1번 주사위 옆면 최대값
    max_side = max([num for num in dice_list[0] if num not in (top, bottom)])
    
    temp = max_side
    
    prev_top = top

 

• for i in range(6)
  • 1번 주사위는 마음대로 놓을 수 있다고 했기 때문에 6면 모두 바닥에 닿도록 둘 수 있다.
  • 바닥에 닿은 면이 바뀔 때마다 쌓은 주사위 옆면의 합 중 최대를 찾는 과정을 반복해야 한다.
• top, bottom = dice_list[0][pair_idx[i]], dice_list[0][i]
  • 1번 주사위의 윗면과 밑면을 바꿔 가면서 배치하는 과정을 처리하는 코드다.
• max_side = max([num for num in dice_list[0] if num not in (top, bottom)])
  • 윗면과 아랫면이 정해지면 옆면도 자연스럽게 정해지게 된다.
  • 1)에서도 언급했듯이 옆면 값 중 최댓값에만 관심이 있기 때문에 max()를 활용했다.
• temp = max_side / prev_top = top
  • temp = max_side: 1번 주사위 배치가 바뀔 때마다 각 주사위의 옆면 최댓값을 더해주기 위한 변수로 초기값은 1번 주사위의 옆면 중 최댓값이다.
  • prev_top = top: i번째 주사위의 윗면에 적힌 숫자와 i+1번째 주사위의 밑면에 적힌 숫자가 같아야 하는 조건을 처리하기 위해 이전 주사위의 윗면 값 저장 목적으로 사용한 변수다.

 

③ 2번 주사위부터 쌓기

for j in range(1, len(dice_list)):
    current_bottom_idx = dice_list[j].index(prev_top)
    
    current_top = dice_list[j][pair_idx[current_bottom_idx]]
    
    temp += max([num for num in dice_list[j] if num not in (current_top, dice_list[j][current_bottom_idx])])
    
    prev_top = current_top

 

• for j in range(1, len(dice_list)
  • 2번 주사위부터 쌓아주는 과정이다.
• current_bottom_idx = dice_list[j].index(prev_top)
  • i번째 주사위의 밑면에 적힌 숫자와 이제 쌓아 올려야 하는 i+1번째 주사위의 윗면에 적힌 숫자가 같아야 하기 때문에 이전에 기록해두었던 prev_top 값을 이용해 A~F면 중 어떤 면이 밑으로 와야 하는지 확인한다.
• current_top = dict_list[j][pair_idx[current_bottom_idx]]
  • 현재 밑면과 마주보는 면을 찾기 위한 부분으로, 1번 주사위에서 사용한 로직과 동일하다.
• prev_top = current_top
  • 한 주사위를 쌓고 나면 윗면의 값을 가장 최근 주사위의 윗면 값으로 갱신해준다.
  • 이 값을 기준으로 다음 주사위가 쌓아져야 한다.

 

3) 전체 코드

import sys

input = sys.stdin.readline

N = int(input())

dice_list = [list(map(int, input().split())) for _ in range(N)]

answer = 0

pair_idx = [5, 3, 4, 1, 2, 0]

for i in range(6):
    top, bottom = dice_list[0][pair_idx[i]], dice_list[0][i]
    
    # 1번 주사위 옆면 최대값
    max_side = max([num for num in dice_list[0] if num not in (top, bottom)])
    
    temp = max_side
    
    prev_top = top
    
    # 2번 주사위부터 쌓기
    for j in range(1, len(dice_list)):
        current_bottom_idx = dice_list[j].index(prev_top)
        
        current_top = dice_list[j][pair_idx[current_bottom_idx]]
        
        temp += max([num for num in dice_list[j] if num not in (current_top, dice_list[j][current_bottom_idx])])
    
        prev_top = current_top
        
    answer = max(answer, temp)
    
print(answer)

 

4) 어려웠던 점/배운 점

🚨 어려웠던 점

• 처음에는 문제에 주어진 그림만 보고 A가 무조건 윗면, F가 무조건 밑면이라고 생각해서 구현 방법을 떠올리는 데에 어려움이 있었다.

❗ 배운 점

• 어려워보이는 문제라고 겁먹지 말고 로직을 잘 세우자. 로직만 깔끔하게 나오면 그대로 구현하기만 하면 됨 🤟