[백준] 비즈 공예

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

1301번: 비즈 공예

 

import sys

#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n = int(input())

marble = [0] * 6

for i in range(n):
    marble[i] = int(input())

dp = [
    [[[[[[-1 for _ in range(6)]
        for __ in range(6)]
    for ___ in range(11)]
    for ____ in range(11)]
    for _____ in range(11)]
    for ______ in range(11)]
    for _______ in range(11)
]

total = sum(marble)

def recur_dp(cnt, prev_color, cur_color):
    if cnt == total:
        return 1
    
    val = dp[marble[0]][marble[1]][marble[2]][marble[3]][marble[4]][prev_color][cur_color]

    if val != -1:
        return val

    ret = 0
    for i in range(n):
        if i == prev_color or i == cur_color or marble[i] == 0:
            continue

        marble[i] -= 1
        ret += recur_dp(cnt + 1, cur_color, i)
        marble[i] += 1

    dp[marble[0]][marble[1]][marble[2]][marble[3]][marble[4]][prev_color][cur_color] = ret
    return ret


# 아무 관련 없는 색상을 넣어준다.
print(recur_dp(0, 5, 5))