반응형 knuth 썸네일형 리스트형 [BOJ 11066] 파일 합치기 (https://www.acmicpc.net/problem/11066) 이 문제는 Dynamic Programming을 이용하는 문제이며, Knuth's Optimization을 이용하여 최적화를 한다. Knuth's Optimization 게시글 (https://wogud6792.tistory.com/20) 위 문제는 파일을 합치는 모든 경우 중에서, 합이 최소가 되는 경우를 찾는 문제이다. 만약 C1~C4를 합친다면, C1 + C2~C4 또는, C1~C2 + C3~C4 또는, C1~C3 + C4와 같이 부분문제가 만들어질 수 있다. 이 때, C2 ~ C4, C1 ~ C3의 경우도 또 다시 부분문제로 나뉘어 질 수 있다. ex) C2 + C3~C4 또는 C2~C3 + C4 / C1 + C2~C3 또는 .. Knuth's Optimization Knuth's Optimization은 Dynamic Programming의 점화식이 아래와 같은 특정 조건을 만족하는 경우 사용할 수 있는 "최적화" 기법이다. i) DP 점화식 형태 $ dp[i][j] = min(dp[i][k] + dp[k+1][j]) + C[i][j] $ $ (i\le k 이전 1 다음
