코드 복사/붙여넣기 하는 당신이 아름답습니다.

4243 : 보안 업체

풀이

내가 지금 [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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-09-17 12:15

Read more posts by this author