백준 11066 c++

코딩테스트 준비 2022. 6. 23. 20:01

11066번: 파일 합치기

소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본

www.acmicpc.net

순차적으로 더해가며 합의 최소값을 찾는 방법이므로 순서대로 표를 그려 동적계획법으로 풀려고 함.

기본적인 동적계획법 문제인 냅색문제(배낭문제)는 차례로 하면 되는데

파일 합치기는 1 /2 3/ 4 , 1 2 / 3 /4, 1 2/ 3 4 의 경우에 따라 답이 달라짐

그러므로 모든 경우를 반복문으로 비교해 가며 최소값을 찾는다 // 이전에 메모이제이션을 통해 시간 단축

차주석 차주석