블로그 이사 중입니다 >> gumgood.github.io

11066 파일 합치기 본문

Problem Solving/문제 풀이

11066 파일 합치기

gumgood 2018. 11. 13. 13:14

C++11


기본 아이디어는 brute force인데 중복 부분 문제가 있으므로 memorization을 이용한다.


dp[i][j] := i부터 j번째 파일들을 하나로 합치는데 드는 최소 비용 (i < j)

sum(i,j) := i부터 j번째 파일들의 크기의 합 (부분합을 전처리로 계산해놓으면 O(1)에 구할 수 있다)


이라고 했을 때,


1) i==j 이면 파일이 하나이므로 dp[i][j] = 0


2) j-i == 1 이면 파일이 두 개이므로  dp[i][j] = sum(i,j)


3) 나머지의 경우,

    dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i,j)) (i <= k < j)


O(n^2)


recursive dp로 간략하게 구현하였다

iterative하게도 구현할 수 있긴 하다.

'Problem Solving > 문제 풀이' 카테고리의 다른 글

2903 중앙 이동 알고리즘  (0) 2018.11.13
1351 무한 수열  (0) 2018.11.13
11066 파일 합치기  (0) 2018.11.13
15483 최소 편집  (0) 2018.11.13
5430 AC  (0) 2018.11.13
1966 프린터 큐  (0) 2018.11.13
0 Comments
댓글쓰기 폼