풀이
dp[i][j][k][d] = (i, j)까지 방향을 k번 틀고 d방향에서 왔을 때의 최소 연료량
아 졸리다 자세한 풀이는 다른 블로그를 보는 게 더 좋겠다!
코드
#include <stdio.h>
#include <string.h>
int min(int a, int b) { return a < b ? a : b; }
int n, m, l, g, dp[102][102][102][2], gas[102][102][2];
int main() {
int T;
for (scanf("%d", &T); T; T--) {
scanf("%d %d %d %d", &n, &m, &l, &g);
for (int i = 1; i <= n; i++) {
for (int j = 1; j < m; j++) {
scanf("%d", &gas[i][j][0]);
}
}
for (int i = 1; i < n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &gas[i][j][1]);
}
}
memset(dp, 0x3f, sizeof(dp));
dp[1][1][1][0] = dp[1][1][1][1] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 1; k <= 100; k++) {
int &d0 = dp[i][j][k][0], &d1 = dp[i][j][k][1];
int g0 = gas[i][j-1][0], g1 = gas[i-1][j][1];
int r0 = min(dp[i][j-1][k][0], dp[i][j-1][k-1][1]);
int r1 = min(dp[i-1][j][k][1], dp[i-1][j][k-1][0]);
d0 = min(d0, r0 + g0);
d1 = min(d1, r1 + g1);
}
}
}
int ans = -1;
for (int k = 100; k; k--) {
if (dp[n][m][k][0] <= g) ans = k;
if (dp[n][m][k][1] <= g) ans = k;
}
printf("%d\n", ~ans ? (n + m - 2) * l + ans - 1 : -1);
}
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이