풀이
내가 지금 [left, right] 구간을 방문한 상태라고 하면,
다음 상태는 [left-1, right] 또는 [left, right+1]가 될 것이다.
이를 토대로 다이나믹 프로그래밍을 해주자.
단, 다음 두 상태로 나아갈 때 left에 서있는지 right에 서있는지에 따라 거리합이 달라지므로
이를 유의해서 코드를 짜보자.
코드
#include <cstdio>
#include <cstring>
typedef long long ll;
int tc, n, s, a[102];
ll dp[2][102][102];
ll min(ll a, ll b) { return a<b?a:b; }
ll dst(int x, int y) { return a[y]-a[x]; }
int main() {
for (scanf("%d", &tc); tc--;) {
scanf("%d %d", &n, &s);
for (int i = 2; i <= n; i++) {
scanf("%d", &a[i]);
a[i] += a[i-1];
}
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
dp[0][i][j] = dp[1][i][j] = 1e18;
dp[0][s][s] = dp[1][s][s] = 0;
for (int i = s; i >= 1; i--) {
for (int j = s; j <= n; j++) {
if (i == j) continue;
int c = n-j+i;
dp[0][i][j] = min(dp[0][i+1][j]+c*dst(i,i+1), dp[1][i+1][j]+c*dst(i,j));
dp[1][i][j] = min(dp[1][i][j-1]+c*dst(j-1,j), dp[0][i][j-1]+c*dst(i,j));
}
}
printf("%lld\n", min(dp[0][1][n], dp[1][1][n]));
}
return 0;
}
#include <cstdio>
typedef long long ll;
int tc, n, s, a[101];
ll dp[2][101][101];
ll min(ll a, ll b) { return a<b?a:b; }
ll dst(int x, int y) { return a[y]-a[x]; }
ll go(int t, int x, int y) {
if (x == 1 && y == n) return 0;
if (dp[t][x][y] != 1e18) return dp[t][x][y];
ll ret = 1e18, pos = t ? y : x, c = n-y+x-1;
if (x > 1) ret = min(ret, go(0, x-1, y) + c * dst(x-1, pos));
if (y < n) ret = min(ret, go(1, x, y+1) + c * dst(pos, y+1));
return dp[t][x][y] = ret;
}
int main() {
for (scanf("%d", &tc); tc--;) {
scanf("%d %d", &n, &s);
for (int i = 2; i <= n; i++) {
scanf("%d", &a[i]);
a[i] += a[i-1];
}
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
dp[0][i][j] = dp[1][i][j] = 1e18;
printf("%lld\n", go(0, s, s));
}
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이