Baekjoon [2116] 주사위 쌓기 - python

문제

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

2116번: 주사위 쌓기

 

코드 풀이

import copy
import sys
sys.setrecursionlimit(10**6)


n = int(input())
n_dice = []
total_dice = []
depth =0
summ_dice = 0
for i in range(n):
    n_dice.append(list(map(int,input().split())))

def sum_dice(idx,depth):
    global summ_dice
    # print(idx,depth)
    # print(summ_dice)
    # print(test_dice)
    if depth  >= n:
        print("yes")
        return summ_dice
    if idx == 0:
        new_idx = 5
        start_idx = test_dice[depth][idx]
        end_idx = test_dice[depth][new_idx]
        if depth +1 >= n:
            # print(depth)
            test_dice[depth].remove(start_idx)
            test_dice[depth].remove(end_idx)
            max_num = max(test_dice[depth])
            summ_dice += max_num
            return summ_dice
        target_idx = test_dice[depth+1].index(end_idx)
        # print(target_idx)
        test_dice[depth].remove(start_idx)
        test_dice[depth].remove(end_idx)
        max_num = max(test_dice[depth])
        summ_dice += max_num
        depth +=1
        # print(n_dice)
        # print(test_dice[depth].index(new_idx))
        return sum_dice(target_idx,depth)
    elif idx == 1:
        new_idx = 3
        start_idx = test_dice[depth][idx]
        end_idx = test_dice[depth][new_idx]
        if depth + 1 >= n:
            # print(depth)
            test_dice[depth].remove(start_idx)
            test_dice[depth].remove(end_idx)
            max_num = max(test_dice[depth])
            summ_dice += max_num
            return summ_dice
        target_idx = test_dice[depth+1].index(end_idx)
        test_dice[depth].remove(start_idx)
        test_dice[depth].remove(end_idx)
        max_num = max(test_dice[depth])
        summ_dice += max_num
        depth +=1

        return sum_dice(target_idx,depth)
    elif idx == 2:
        new_idx = 4
        start_idx = test_dice[depth][idx]
        end_idx = test_dice[depth][new_idx]
        if depth + 1 >= n:
            # print(depth)
            test_dice[depth].remove(start_idx)
            test_dice[depth].remove(end_idx)
            max_num = max(test_dice[depth])
            summ_dice += max_num
            return summ_dice
        target_idx = test_dice[depth+1].index(end_idx)
        test_dice[depth].remove(start_idx)
        test_dice[depth].remove(end_idx)
        max_num = max(test_dice[depth])
        summ_dice += max_num
        depth +=1

        return sum_dice(target_idx,depth)
    elif idx == 3:
        new_idx = 1
        start_idx = test_dice[depth][idx]
        end_idx = test_dice[depth][new_idx]
        if depth + 1 >= n:
            # print(depth)
            test_dice[depth].remove(start_idx)
            test_dice[depth].remove(end_idx)
            max_num = max(test_dice[depth])
            summ_dice += max_num
            return summ_dice
        target_idx = test_dice[depth+1].index(end_idx)
        test_dice[depth].remove(start_idx)
        test_dice[depth].remove(end_idx)
        max_num = max(test_dice[depth])
        summ_dice += max_num
        depth +=1

        return sum_dice(target_idx,depth)
    elif idx == 4:
        new_idx = 2
        start_idx = test_dice[depth][idx]
        end_idx = test_dice[depth][new_idx]
        if depth + 1 >= n:
            # print(depth)
            test_dice[depth].remove(start_idx)
            test_dice[depth].remove(end_idx)
            max_num = max(test_dice[depth])
            summ_dice += max_num
            return summ_dice
        target_idx = test_dice[depth+1].index(end_idx)
        test_dice[depth].remove(start_idx)
        test_dice[depth].remove(end_idx)
        max_num = max(test_dice[depth])
        summ_dice += max_num
        depth +=1

        return sum_dice(target_idx,depth)
    elif idx == 5:
        new_idx = 0
        start_idx = test_dice[depth][idx]
        end_idx = test_dice[depth][new_idx]
        if depth + 1 >= n:
            # print(depth)
            test_dice[depth].remove(start_idx)
            test_dice[depth].remove(end_idx)
            max_num = max(test_dice[depth])
            summ_dice += max_num
            return summ_dice
        target_idx = test_dice[depth+1].index(end_idx)
        test_dice[depth].remove(start_idx)
        test_dice[depth].remove(end_idx)
        max_num = max(test_dice[depth])
        summ_dice += max_num
        depth +=1

        return sum_dice(target_idx,depth)
for i in range(6):
    test_dice = copy.deepcopy(n_dice)
    depth = 0
    summ_dice = 0
    b = sum_dice(i,depth)
    total_dice.append(b)
# print(total_dice)
print(max(total_dice))

 

문제 접근

주사위 면이 주어지고, 쌓인 주사위에서 그리디 알고리즘을 통해 옆면의 최대 합을 구하는 문제입니다. 문제 접근을 다음과 같이 진행했습니다.

 

1. 주사위를 각각 쌓는다.

2. 0번째 idx는 5번째 idx와 마주보고, 1번째 idx는 3번째 idx와 마주보고, 2번째 idx는 4번째 idx와 마주본다.

3. 주사위 탐색을 진행한다. 이때 주사위 층은 depth변수를 통해 접근하며 마지막 depth만 예외처리를 따로 진행한다.

4. 주사위를 탐색하며 최대값을 계산한다. 이때 위에 면과 아래면을 계산하기 위해 start_idx, end_idx로 값을 계산하며 idx를 계산한다. 

5. 구한 idx를 한 depth에 있는 주사위 값에서 빼며 위,아래 곂친 면을 제외하고 4개의 옆면에서 최대값을 구한다. 

6. 4번과 5번을 지속적으로 반복하며 최대값을 합한 후, 최종 리스트에 추가한다.

7. 최종 리스트에서 최대 값을 도출한다.

 

위 방식으로 진행하며 문제를 접근했습니다. 이해가 안되시면 댓글 남겨주시면 감사하겠습니다.