[백준] 11066 파일 합치기

문제

• 연속하는 두 파일을 합치는데 필요한 비용은 두 파일 크기의 합이다.
• 파일이 K개 주어질 때 파일을 하나로 합칠 때 필요한 최소비용 구하기

 

• 3 <= K <= 500
  파일 크기 <= 10,000

 

풀이

• dp[i][j] : i~j 파일을 합치는데 최소 비용
  • dp[i][i] => 자기 자신 ( f[i] - f[i-1] )
  • dp[i][i+1] => 두 파일의 합 ( f[i+1] - f[i-1] )
  • dp[a][b] =  dp[a][k] + dp[k+1][b] + sum(f[a]~f[b])
    -> 단, 파일이 하나인 경우 제외

pypy로 통과

for _ in range(int(input())) :
    K = int(input())
    f = [0] + list(map(int, input().split()))
    # f 누적합
    for i in range(1, K+1) :
        f[i] += f[i-1]
    
    # dp[i][j] : i~j 파일을 합치는데 최소 비용
    dp = [[1e9]*(K+1) for _ in range(K+1)]
    for i in range(1, K) :
        dp[i][i] = f[i]-f[i-1]
        dp[i][i+1] = f[i+1]-f[i-1]
    dp[K][K] = f[K]-f[K-1]

    for c in range(2, K) :          # 파일의 개수
        for s in range(1, K+1-c) :  # 파일 시작점
        	# dp[a][k] = dp[k+1][b] + sum(f[a]~f[b])
            dp[s][s+c] = min(dp[s+1][s+c], dp[s][s+c-1]) + f[s+c]-f[s-1]
            for k in range(s+1, s+c-1) :
                dp[s][s+c] = min(dp[s][s+c], dp[s][k] + dp[k+1][s+c] + f[s+c]-f[s-1])

    print(dp[1][K])

 

References

• 백준 오늘의 문제