반응형
11066
-
BOJ) 파일 합치기 (11066 번)알고리즘/백준 2021. 2. 2. 18:22
파일 합치기 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net DP로 분류된 문제인데, 정답률에 비해 굉장히 어렵게 느껴졌다. 연속된 소설 파일들을 합치는데, 연속이 되도록 파일을 합쳐야한다. 즉, 인접한 두 파일만을 합칠 수 있을 때, 가장 최소 비용을 구하는 문제다. 이 문제는 풀지 못했다. 정말 모르겠어서 다른 분들의 풀이를 참고해서 블로그를 포스팅한다. 참고한 링크는 하단에 걸어두었다. dp[i][j]는 i부터 j까지 합쳐지는데 최솟값을 저장한다. ( i ~ j 장 까지 합치는데 드는 최소 비용)..