백준 : https://www.acmicpc.net/problem/11066
문제 이해하기
와… 저는 처음에 이 문제보고 풀 수 있겠구나 생각했습니다. 왜냐면 ‘262가지 문제로 정복하는 코딩 인터뷰’ 라는 책에서 본 거 같았으니까 말이죠. 그래서 음.. 그냥 정렬, 구현 문제인가 싶었습니다. 그래서 문제를 풀면서 가설을 세우면서 접근했습니다.
지금 생각해보면 문제도 제대로 읽지 않았던거 같았네요. 문제에서는 “소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다.” 그니까 파일을 합치되 순서는 유지해야 된다는 거를 내포하고 있었습니다. 문제에서 딱 잘라서 설명을 하진 않았지만 챕터 1, 2, 3, 4 장 이 있는데 1과 4를 먼저 합칠 수는 없잖아요? 상식적으로…
그리고 제가 세운 가설은 다 틀렸던거 같습니다. 정렬 자체도 이미 틀렸는데, 아래 가설도 다 맞지 않고...
- 작은거 부터 그룹핑해서 순차적으로 더한다.
- 작은 거 + 큰 거 부터 더한다
- 작은거 부터 더한다음 다시 추가해서 정렬한다음 더한다.
문제 풀이
결국 정답을 보고 말았는데 이 문제는 DP 문제였습니다… 아… 진짜 DP는 제가 정말 못푸는 거 같네요…
참고 : https://data-make.tistory.com/402 (정말 많은 도움이 되었습니다. )
step 1. 누적합 구하기
일단, 누적합을 먼저 구해야 합니다. 누적합 혹은 구간합(preifx sum)이라고 불리는 개념은 부분합과는 좀 다릅니다. 제가 이전에 쓴 글 참고 : https://velog.io/@ckstn0778/백준-10986번-나머지-합-X-1-Python
입력이 [40 30 30 50]와 같을 때, 이렇게 누적합을 구하면 [0, 40, 70, 100, 150]가 됩니다. 이렇게 누적합을 먼저 구하는 이유는 앞으로 나오는 계산을 쉽게 하기 위해서입니다. 이렇게 하면 효율적이기 때문이죠.
step 2. DP 배열 생성 및 파일 2개씩 합치는 경우
그리고 나서 DP 배열은 만들어 줍니다. DP[i][j]는 i에서 j까지 합하는데 필요한 최소 비용이 됩니다. 실제로는 0은 안쓰이는 부분. 1부터 쉽게 계산하기 위해서.
이제 파일이 2개씩 합칠때를 봅시다. (1, 2), (2, 3), (3, 4)로 나눌 수 있습니다. 각각, 70, 60, 80이 됩니다.
step 3. 파일 3개씩 합치는 경우
다음으로 파일을 3개씩 합칠때는 보자. 1~3을 합치는 경우와 2~4를 합치는 경우가 있지.
일단, 1~3을 합치는 경우를 생각해보자. 2가지를 생각해볼 수 있어. (1, 2~3)과 (1~2, 3) 임. 이 경우 최소가 되도록 더하는 걸 어떻게 계산할 수 있을지 생각해보자. min(2~3, 1~2) + 1~3 누적합이 아닐까? 잘 생각해봐. 일단 뭐가 됐든 1~3을 다 더한 값 100은 고정이야. 그렇다면 2와 3을 더한게 더 좋을까 1와 2를 더한게 더 좋을까 생각해봐야지. 그래서 수식은 min(2~3, 1~2) + 1~3 누적합이 되는거야.
마찬가지로 2~4를 합치는 경우도 계산해볼 수 있어. 그 결과가 아래 DP야.
step 4. 파일 4개씩 합치는 경우
자. 거의 다 왔어. 마지막으로 파일 4개씩 합쳐야 돼. (1 +,2,3,4), (1,2 + 3,4), (1,2,3 + 4) 파일로 나눌 수 있는데, 이것도 동일하게 구할 수 있어. min(2~4, 1~2 + 3~4, 1~3) + 1~4 누적합이 되는거지. 2~4, 1~2 + 3~4, 1~3은 이전 DP에서 구했으니까 쉽게 구할 수 있지.
어떻게 이런 생각을 했을까 정말 놀라운거 같네요... DP문제를 풀려면 기본적으로 많이 익숙해지고 머리도 좋아야 하나 봅니다..ㅠ
