BOJ 4243 - 보안 업체

문제 태그 : https://www.acmicpc.net/problem/4243

문제 설명

문제 풀이 (사고의 흐름)

일단 DP라는 것을 어느정도 바로 생각할 수 있었다. 직선에서 하는 DP인데 N이 작기 때문에 N^2이라고 생각을 했고, 이러면 보통 DP[i][j]는 i에서 j까지 ~~~ 라고 생각했다. 여기서 우리는 i 부터 j까지 다 들렀다면 당연히 최종위치는 i또는 j라는 것을 알 수 있다. 들르는데 걸리는 시간은 0이기 때문에 중간에 띄고 건널 이유가 아예없다. 그래서 관찰한 사실을 토대로 DP[state][i][j]는 state의 방향에 있으면서 i부터 j까지 들리는데 기다림의 합의 최소라고 생각할 수 있다.

하지만 이러면 문제가 있다. 지금까지 대기시간의 총합이 최소가 되는 경우가 지금까지 걸린 시간의 총합이 되는 경우가 아닐 수 있다. 즉 부분의 최적이 전체의 최적임이 보장이 안된다. 이 경우는 DP가 성립이 안된다. 추가적으로 관찰을 해야한다. 내가 맨처음에 5만큼을 이동하였으면 내 남은 모든 장소에 대한 대기시간이 5 증가한다. 따라서 거리 * 남은 시간으로써 고려를 해준다면 항상 현재 시점을 0으로 생각해 줄 수 있다. 그래서 dp[state][i][j] i~j 까지 완료하였고, state의 방향에 있으며 현재 시점을 0으로 생각하여 남은 곳 들을 모두 들리는데 걸리는 대기시간의 최솟값으로 정의를 할 수 있다. 또한 나는 (i,j)에서 (i-1,j) 또는 (i,j+1)로만 이동 가능하다.

시간복잡도는 O(n^2)

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
ll pre[505][505];
ll dp[2][505][505];
ll n;
 
ll sol(ll l,ll r,ll pos){
    if(dp[pos][l][r]!=1e18) return dp[pos][l][r];
    if(l==1&&r==n) return 0;
    ll &ret=dp[pos][l][r];
    ll now;
    if(pos==0) now=l;
    else now=r;
    if(l>1)
        ret=min ( sol(l-1,r,0)+pre[l-1][now]* (n-(r-l+1)),ret);
    if(r<n)
        ret=min (ret, sol(l,r+1,1)+pre[now][r+1]*(n-(r-l+1)) );
    return ret;
}  
 
int main(){
    ll t;
    scanf("%lld",&t);
    while(t--){
        ll i,j,k,l,m;
        scanf("%lld %lld",&n,&m);
        for(i=1;i<n;i++)
            scanf("%lld",&pre[i][i+1]);
        
        for(i=1;i<=n;i++)
            for(j=i+2;j<=n;j++)
                pre[i][j]=pre[i][j-1]+pre[j-1][j];
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++){
                dp[0][i][j]=1e18;
                dp[1][i][j]=1e18;
            }
        printf("%lld\n",min(sol(m,m,0),sol(m,m,1)));
        
    }
}