[백준][Python] 19949 영재의 시험

재귀 dp로 안쪽에서부터 경우의 수를 뽑아오며 밖으로까지 cnt 값을 누적시켜 꺼내왔습니다.

 

import sys
input = sys.stdin.readline

ans = list(map(int, input().split()))
dp = [[[[-1 for score in range(11)] for pre2 in range(6)] for pre in range(6)] for depth in range(11)]

def make_dp(depth, pre, pre2, score):
    if dp[depth][pre][pre2][score] != -1:
        return dp[depth][pre][pre2][score]

    if depth == 10:
        return 1 if score >= 5 else 0

    cnt = 0
    for next_num in range(1, 6):
        if pre == pre2 and pre2 == next_num:
            continue
        if ans[depth] == next_num:
            cnt += make_dp(depth + 1, pre2, next_num, score + 1)
        else:
            cnt += make_dp(depth + 1, pre2, next_num, score)
    
    dp[depth][pre][pre2][score] = cnt
    return cnt

print(make_dp(0, 0, 0, 0))