<유사문제>
11066 파일 합치기 https://www.acmicpc.net/problem/11066
행렬은 곱셈에 대해 결합법칙이 성립한다. 따라서 값은 같지만 곱셈횟수는 결합법칙에 따라 바뀐다.
행렬 A(10*5), B(5*20), C(20*15)를 예로들면
(A(BC)) = 10*5*15 + (5*20*15) = 2250
((AB)C) = (10*5*20) + 10*20*15 = 4000 임을 알 수 있다.
주어진 문제에서는 최소 행렬 곱셈횟수를 구하는 문제이다.
이 문제는 dp로 풀 수 있다.
$DP[i][j]$ : 구간[i, j]에서 최소 행렬 곱셈 횟수
$DP[i][j] = min(DP[i][j], DP[i][k] + DP[k+1][j] + d_{i-1}*d_{k}*d_{j})$
$N번째 행렬 : A*B$ 이라면 $d_{N} = A, d_{N+1} = B $
#include <cstdio>
#define min(a,b) ((a)<(b))?(a):(b)
#define INF 987654321
int N;
int dp[502][502];
int d[502];
int main(){
scanf("%d", &N);
scanf("%d%d", &d[0],&d[1]);
for (int n = 1; n < N - 1; n++)
scanf("%d%d", &d[n], &d[n + 1]);
scanf("%d%d", &d[N - 1], &d[N]);
for (int dia = 0; dia < N; dia++){
for (int n = 1; n <= N - dia; n++){
int m = n + dia;
if (n == m){
dp[n][m] = 0;
continue;
}
dp[n][m] = INF;
for (int k = n; k < m; k++){
dp[n][m] = min(dp[n][m], dp[n][k] + dp[k + 1][m] + d[n - 1] * d[k] * d[m]);
}
}
}
printf("%d\n", dp[1][N]);
return 0;
}
| cs |
11066 파일합치기 문제도 최소 행렬 곱셈문제와 비슷하다.
다만 점화식 뒤에 부분이 살짝 다르다.
$DP[i][j]$ : 구간[i, j]의 파일을 하나로 합친 최소비용
$sum[i][j]$ : 구간[i,j]에서 각각의 파일 비용 들의 합
$DP[i][j] = min(DP[i][j], DP[i][k] + DP[k+1][j] + sum[i][j]$
#include <cstdio>
#define min(a,b) ((a)<(b))?(a):(b)
#define INF 987654321
int main(){
int T;
scanf("%d", &T);
while (T--){
int K;
int dp[501][501] = { 0 };
int sum[501] = { 0 };
int c[501];
scanf("%d", &K);
for (int k = 1; k <= K; k++){
scanf("%d", &c[k]);
sum[k] += sum[k - 1] + c[k];
}
for (int dia = 0; dia <= K; dia++){ //끝나는 지점
for (int n = 1; n <= K; n++){
int m = n + dia;
if (n == m || m > K)
continue;
dp[n][m] = INF;
for (int k = n; k < m; k++)
dp[n][m] = min(dp[n][m], dp[n][k] + dp[k + 1][m] + sum[m] - sum[n - 1]);
}
}
printf("%d\n", dp[1][K]);
}
return 0;
}
| cs |
댓글 없음:
댓글 쓰기