문제 설명
https://www.acmicpc.net/problem/11066
동적계획법을 사용해서 푸는 문제. 가능한 조합을 전수조사해서 그 중 minimum 값을 구해 dp 배열을 채워나가면 된다.
점화식을 세우는 과정에서 많은 어려움이 있는 문제이다. 점화식 조건이 어려울 뿐 아니라, 단순히 dp의 이전 인덱스들과의 단순 연산보다 조금 더 심화되었다.
나의 문제 풀이 시도 및 발생한 문제점
- 가능한 모든 조합을 찾아야 한다는 점을 빠르게 캐치하지 못했음(dp 점화식 설계 실패)
문제를 쪼개서 해결해야한다는 점은 이해하고 있었지만, 점화식 설계가 틀렸다.
나의 접근은, 2차원 dp 배열에서 i 인덱스는 '어디까지 보았는가', j 인덱스는 '몇 개를 더했는가' 였고, dp 배열을 업데이트 할 때, 이전의 dp값에 새로운 j 번째 input의 비용을 단순히 더하려고만 했다.
i, j의 설계부터가 실패해서 dp 업데이트 식도 세우지 못했다(자꾸 실패하니까 pair로 해서 이전의 최소값과 무슨 연산을 해야하지? 라는 생각에 빠졌다. 조합이 매번 달라질 수 있다는 점을 인지하지 못했다.) - 이전에는 못 본 유형의 응용 DP문제라 당황했다.
점화식만 어떻게든 세우면 해결할 수 있을거라고 생각했고, 규칙을 찾는 데에 소홀했다. 문제를 아마 100% 이해하지 않고 풀려고 했던 것 같다.
문제점 고찰 및 문제 분석
문제를 다시 이해하자. 문제에 대한 이해를 위해 다음 사진들과 같이 이해해나갔다.
비용에 대한 규칙
문제에서는 '비용'을 계산하는 방식을 제대로 설명해주지 않았다.
'비용 = 더하고자 하는 연속된 페이지의 비용 합'
DP 배열에 대한 규칙
점화식을 설계하기 위해 문제를 어떻게 쪼갤 수 있는지 찾아야 한다.
문제를 쪼갤 수 있는 방식의 핵심은, '연속한 페이지'를 합칠 수 있다는 것에 있다. 연속한 페이지들의 합의 조합을 찾기 위해, 아래와 같이 이해할 수 있다.
위 과정에 따라서 문제를 쪼개어 해결해나가는 과정을 아래에 나타냈다.
완성코드
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
int T, N;
int input_novel[501];
int sum[501];
int dp[501][501];
void Init(){
cin >> N;
fill(input_novel, input_novel+(N+1), 0);
fill(sum, sum+(N+1), 0);
fill(&dp[1][1], &dp[N][N], INT_MAX);
for(int j=1; j<=N; j++){
cin >> input_novel[j];
sum[j] = sum[j-1] + input_novel[j];
}
return;
}
void DP_Init(){
for(int i=1; i<=N; i++)
dp[i][i] = 0;
return;
}
void Print(){
cout << dp[1][N] << '\n';
return;
}
void Solve(){
for(int gap=1; gap<N; gap++){ // gap
for(int i=1; i+gap<=N; i++){ // (sum) from j
int j = i+gap;
for(int m=i; m+1<=j; m++) // (sum) to j
dp[i][j] = min(dp[i][j], (dp[i][m] + dp[m+1][j] + (sum[j] - sum[i-1])));
}
}
return;
}
int main(){
cin >> T;
for(int i=0; i<T; i++){
Init();
DP_Init();
Solve();
Print();
}
return 0;
}
솔직히 문제풀이를 이해하는 데에도 상당한 시간을 썼다.
몇 시간을 쓴건지 모르겠다.
참고 링크
1. https://melonicedlatte.com/algorithm/2018/03/22/051337.html