[백준] 주사위 쌓기 (2116번)

난이도 : Gold5
Link : https://www.acmicpc.net/problem/2116
Tag : 구현, 브루트포스 알고리즘
풀이일자 : 2024년 8월 28일

📌 문제 탐색하기

N : 주사위의 갯수
dice [] : 주사위의 전개도들

이 문제는 주사위를 쌓아 옆면의 숫자의 최대값을 구하는 것이 목표이다.
여기서 조건은 다음과 같다.
1.

전개도는 다음과 같이 주어지며 A~ F 까지 순서대로 입력된다.
2. 주사위를 쌓을 때 아랫 주사위의 윗면 숫자와 윗 주사위의 아래 숫자가 같아야 한다.

이렇게 두가지 조건을 가지고 옆면의 최대값을 구하는 것이 이 문제의 핵심이다.

가능한 시간복잡도

한개의 주사위는 6면을 가지고 있기 때문에 주사위 갯수는 10,000개 이하이므로 시간 복잡도 상 문제는 없을 것으로 판단된다.

📌 문제 접근 방법

문제를 파악했을때의 조건 두가지를 통해 문제를 접근할 수 있다.
1. 주사위의 전개도를 입력받는다.
2. 윗면과 아랫면이 될 수 있는 경우들을 딕셔너리를 통해 접근 할 수 있을것이다.
따라서 다음과 같다.

dict = {    # 마주 보고 있는 주사위의 인덱스 값
    0 : 5,
    1 : 3,
    2 : 4,
    3 : 1,
    4 : 2,
    5 : 0
}

3. 옆면의 최대값의 조건
   • 옆면이 최대값을 갖는 경우를 찾기 위해서는 윗면과 아랫면에 6이 있다면 최대값은 5가 될것이며 6과 5둘다 포함하게 된다면 최대값은 4가 될것이다. 이를 제외한 모든 경우들은 주사위를 돌릴 수 있기 때문에 6이 될것이다.

📌 코드 설계하기

1. n과 cube를 입력받는다.
2. dict를 설정하여 마주 볼 수 있는 인덱스를 매칭한다.
3. side_max(top) 함수를 만든다.
   • 주사위 마다 탐색을 진행하여 top 이 적힌 값을 찾는다.
   • top이 적힌값을 찾았을때 마주보는 면을 bottom으로 설정한다.
   • top 과 bottom에 6이 있다면 최대값 5
   • top 과 bottom에 6과 5가 있다면 최대값 4
   • top 과 bottom에 6이 없다면 최대값을 6으로 설정한다
   • result변수에 최대값을 더하고 다음 주사위의 면을 결정하기 위해 top = bottom으로 업데이트 시킨다.
4. 첫번째 주사위에서 top이 될 수 있는 1~6까지를 넣어보며 side_max의 최대값을 출력한다.

📌 시도 회차 수정 사항

📌 정답 코드

n = int(input())
cube = [list(map(int, input().split())) for i in range(n)]

dict = {    # 마주 보고 있는 주사위의 인덱스 값
    0 : 5,
    1 : 3,
    2 : 4,
    3 : 1,
    4 : 2,
    5 : 0
}

def side_max(top):
    result = 0

    for i in range(n):
        for j in range(6):
            if cube[i][j] == top: #현재 주사위에서 top 이 적힌 값을 찾기
                bottom = cube[i][dict[j]] #적힌값의 반대편
                if 6 in [top,bottom]: # 윗면과 아랫면에 6이 들어갔을때
                    if 5 in [top,bottom]: # 5가 들어갔을때
                        result += 4
                    else:
                        result += 5
                else: # 6이 들어가지 않았을때
                    result += 6
                top = bottom #반대편 값을 업데이트하여 다음 주사위 면 결정
                break
    return result

answer = 0
for i in range(1,7):
    answer = max(answer, side_max(i))

print(answer)