[BOJ] 14238 - 출근 기록 (Python)

 

 

아이디어

 

동적 계획법과 DFS로 순열에서 올바른 출근 기록이 있는지 확인한 후 해당 순열을 만든다.

 

 

풀이

 

dp[a][b][c][p2][p1]에서 a, b, c는 각각 남은 출근 횟수, p1은 전날 출근자, p2는 전전날 출근자를 나타낸다.

 

def solution():

    def dfs(a, b, c, p2, p1):
        if dp[a][b][c][p2][p1]:
            return
        dp[a][b][c][p2][p1] = 1
        if a > 0:
            dfs(a-1, b, c, p1, 0)
        if b > 0 and p1 != 1:
            dfs(a, b-1, c, p1, 1)
        if c > 0 and p1 != 2 and p2 != 2:
            dfs(a, b, c-1, p1, 2)

    S = input()
    N = len(S)
    B, C = S.count('B'), S.count('C')
    A = N-(B+C)
    dp = [[[[[0]*3 for _ in range(3)] for _ in range(C+1)] for _ in range(B+1)] for _ in range(A+1)]
    dfs(A, B, C, 0, 0)
    p1 = -1
    for i in range(3):
        for j in range(3):
            if dp[0][0][0][i][j]:
                p1 = j
    if p1 >= 0:
        str_list = ['A', 'B', 'C']
        cnt_list = [0, 0, 0]
        res = []
        for _ in range(N):
            for p2 in range(3):
                if dp[cnt_list[0]][cnt_list[1]][cnt_list[2]][p2][p1]:
                    res.append(str_list[p1])
                    cnt_list[p1] += 1
                    p1 = p2
                    break
        print(''.join(res[::-1]))
    else:
        print(-1)

solution()