문제

링크텍스트

난관

• 문제를 이해하기 어려웠다.
• 알고리즘 분류가 '다이나믹 프로그래밍'이었지만, 어떻게 머리 속에서 연결이 안되었다.
• 1차로 모든 가능성을 풀어 보았더니 '메모리 초과'가 나왔다.
• 인터넷에서 참조하여 간신히 풀었으나 아직 완전히 이해하지는 ㅠㅠ
• 스트라이커 별로 각점에서의 최적이 과연 나중에도 유지 되나가 아직 갸우뚱하다.
• 항해 3일차 최대 난관이었다!!!

결과

• 1차 틀린 코드

c = int(input())
for i in range(c):
    n, l1, l2, s1, s2 = map(int, input().split())    
    t_cost = [list(map(int, input().split())),    
        list(map(int, input().split())),    
        list(map(int, input().split())),    
        list(map(int, input().split()))]    
    c_i = [l1,l2]
    p_i = [0,1]
    for j in range(n-1):
        p_i0 = p_i
        p_i = []
        c_i0 = c_i
        c_i = []
        for k in range(len(p_i0)):
            p_i.append((p_i0[k]+1)%2)
            c_i.append(t_cost[p_i0[k]*2+0][j]+c_i0[k])
            p_i.append(p_i0[k])
            c_i.append(t_cost[p_i0[k]*2+1][j]+c_i0[k])
    c_s = [s1,s2]
    for j in range(len(c_i)):
        c_i[j] += c_s[p_i[j]]
    Z = min(c_i)
    print(Z)

• 최종 코드

c = int(input())
for i in range(c):
    n, l1, l2, s1, s2 = map(int, input().split())    
    t_cost = [list(map(int, input().split())),    
        list(map(int, input().split())),    
        list(map(int, input().split())),    
        list(map(int, input().split()))]    
    c_i = [[0]*n,[0]*n]
    c_i[0][0] = l1
    c_i[1][0] = l2
    for j in range(n-1):
        c_i[0][j+1] = min(c_i[1][j]+t_cost[2][j], c_i[0][j]+t_cost[1][j])
        c_i[1][j+1] = min(c_i[0][j]+t_cost[0][j], c_i[1][j]+t_cost[3][j])
    Z = min([c_i[0][n-1] + s1,c_i[1][n-1] + s2])
    print(Z)