[BOJ] 11066. 파일합치기(DP).py,.cpp

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

DP의 가장 어려운 유형의 문제

이 문제의 기본적인 idea만 알아도 다른 문제에 많이 활용할 수 있다고 한다.

입력이 아래와 같을 때,

4

40 30 30 50

먼저 누적합을 구해주면 아래 list와 같다.

[0, 40, 70, 100, 150]

누적합을 구해주는 이유는 두 개의 파일을 합칠 때 필요한 비용(두 파일 크기의 합)을 

편하게 연산하기 위함이다.

이 문제는 DP를 정의하는게 정말 어렵다.

먼저 DP는 2차원 배열을 사용할 것이고,

DP[i][j]는 i에서 j까지 합하는데 필요한 최소 비용이 된다.

파일 한 개(파일의 길이 : 1)는 비용이 들지 않으므로 비용이 0이고, 

파일의 길이가 2일 경우부터 4일 경우까지 비용을 확인해보아야 한다.

예를 들어 파일의 길이가 3일 경우는 파일을 합치는 방법을 

(1번) + (2번,3번)인 경우와 (1번, 2번) + (3번)인 경우로 나눌 수 있다.

이렇게 나눠보기 위해 기존의 두 파일을 합치는 비용이 미리 계산되어 있어야 한다.

누적합 S = [0, 40, 70, 100, 150]

길이가 2일 경우,

(1,2), (2,3), (3,4) 파일로 나눌 수 있는데,

1번부터 2번파일까지의 비용은 (1~1의 비용(0) + 2~2의 비용(0)) + (1~2까지 누적합(70)) = 70 이 되고,

2번부터 3번파일까지의 비용은 (2~2의 비용(0) + 3~3의 비용(0)) + (2~3까지 누적합(60)) = 60 이 되고,

3번부터 4번파일까지의 비용은 (3~3의 비용(0) + 4~4의 비용(0)) + (2~3까지 누적합(80)) = 80 이 된다.

여기서 DP[][]의 상태는 아래 그림과 같다.

다음 길이가 3일 경우,

(1 + 2,3), (1,2 + 3), (2, + 3,4), (2,3 + 4) 파일로 나눌 수 있는데

1번부터 3번파일까지의 비용은 min(1~1의 비용(0) + 2~3의 비용(60).

 1~2의 비용(70) + 3~3의 비용(0)) 

+ (1~3까지의 누적합(100)) = 160 이 된다.

2번부터 4번파일까지의 비용은 min(2~2의 비용(0) + 3~4의 비용(80).

 2~3의 비용(60) + 4~4의 비용(0)) 

+ (2~4까지의 누적합(110)) = 170 이 된다.

마지막으로 길이가 4일 경우,

(1 +,2,3,4), (1,2 + 3,4), (1,2,3 + 4) 파일로 나눌 수 있는데,

1번부터 4번파일까지의 비용은 min(1~1의 비용(0) + 2~4의 비용(170).

 1~2의 비용(70) + 3~4의 비용(80),

 1~3의 비용(160) + 4~4의 비용(0))

 + (1~4까지의 누적합(150)) = 300 이 된다.

여기서 마지막으로 1~4번까지의 파일을 합쳐야 하므로

DP[1][N]을 출력해주면 된다.

여기서 찾을 수 있는 점화식은

DP[i][k] + DP[k+1][j] + sum(A[i]~A[j]) 가 될 것이다.

(i~k)까지 비용의 합과 그 다음 (k+1지점부터 마지막 지점)까지의 합의 최소에

(i~j)까지의 누적합을 더해주면 얻고자하는 해를 얻을 수 있다.

여기서 DP[][]는 i부터 j까지 파일을 합치는데 드는 비용으로 정의하고 푸는 것이 중요한 포인트인것 같다.

#. Python Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

def solve():     N, A = int(input()), [0] + list(map(int, input().split()))     # S[i]는 1번부터 i번까지의 누적합     S = [0 for _ in range(N+1)]     for i in range(1, N+1):         S[i] = S[i-1] + A[i]       # DP[i][j] : i에서 j까지 합하는데 필요한 최소 비용     # DP[i][k] + DP[k+1][j] + sum(A[i]~A[j])     DP = [[0 for i in range(N+1)] for _ in range(N+1)]     for i in range(2, N+1): # 부분 파일의 길이         for j in range(1, N+2-i):   # 시작점             DP[j][j+i-1] = min([DP[j][j+k] + DP[j+k+1][j+i-1] for k in range(i-1)]) + (S[j+i-1] - S[j-1])       print(DP[1][N])   for _ in range(int(input())):     solve() Colored by Color Scripter

cs