[BOJ] 11066. 파일합치기 ( python, 그림낙서, DP, 회고록 )

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

11066번: 파일 합치기

 

DP는 풀어도 적응이 안되고, 난이도가 높아지면 높아질수록 적용방법을 모르겠다

 

이 문제를 풀 때, 

1. 순서에 따라 계산을 하면 결과가 달라지기 때문에 조합을 이용해야 할 것 같다
2. 조합되는 개수가 홀수, 짝수에 의해 달라지는 최솟값을 도출해야 할 것 같다
3. 연속되는( 3 다음에 3과 같은 연속 ) 숫자를 기반으로 찾아 최솟값을 추론할 수 있을 것 같다

라고 생각했다. 

 

결론적으로는 1번 조합을 추론한 것 제외한 나머지들은 유용하지 않은 생각이었다.

 

그러면 나는 이 문제들을 다음에 적용할 수 있게 이 문제를 어떻게 바라봐야 할까?

1. 이 문제가 조합임을 이해하고, DP에 각 조합들의 합계를 저장할 수 있을 것 같다
2. 조합되는 개수가 홀수, 짝수 와는 별개로 조합의 순서에 따른 계산값을 DP에 녹여낼 수 있어야 할 것 같다

음.. 다음에 이런 비슷한 문제를 보더라도 또 헤맬 것 같다..

 

 

N = int(input())

for _ in range(N):
    total = int(input())
    num_list = [0] + list(map(int,input().split() ))

    prefix_sum = [0]

    for i in range(1,len(num_list)):
        prefix_sum.append( prefix_sum[-1] + num_list[i])

    dp = [ [0] * len(num_list) for _ in range(len(num_list)) ]

    for length in range(2, total+1):
        for start in range( 1, total-length+2):
            end = start + length - 1
            dp[start][end] = min( [ dp[start][mid] + dp[mid+1][end] for mid in range(start,end)] ) + prefix_sum[end] - prefix_sum[start-1]
    print(dp[1][-1])