Submission #7596

#	Time	Username	Problem	Language	Result	Execution time	Memory
7596		jihoon	배열 탈출 (GA8_array)	C++98	100 / 100	664 ms	39660 KiB

array

#include<cstdio>
#include<algorithm>
#define inf 2100000000
using namespace std;

int bae[2222][2222];
int dp[2222][2222];
int n;

int main(){
    int i,j;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            dp[i][j]=inf;
            scanf("%d",&bae[i][j]);
        }
    }
    dp[0][0]=0;
    for(i=0;i<n-1;i++){
        for(j=0;j<n-1;j++){
            if(bae[i][j]>bae[i][j+1]){
                dp[i][j+1]=min(dp[i][j+1],dp[i][j]);
            }else{
                dp[i][j+1]=min(dp[i][j+1],bae[i][j+1]-bae[i][j]+1+dp[i][j]);
            }
        }
        for(j=0;j<n;j++){
            if(bae[i][j]>bae[i+1][j]){
                dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
            }else{
                dp[i+1][j]=min(dp[i+1][j],bae[i+1][j]-bae[i][j]+1+dp[i][j]);
            }
        }
    }
    for(j=0;j<n-1;j++){
        if(bae[i][j]>bae[i][j+1]){
            dp[i][j+1]=min(dp[i][j+1],dp[i][j]);
        }else{
            dp[i][j+1]=min(dp[i][j+1],bae[i][j+1]-bae[i][j]+1+dp[i][j]);
        }
    }
    printf("%d",dp[n-1][n-1]);
}

• Subtask 1: 6 / 6
• Subtask 2: 11 / 11
• Subtask 3: 32 / 32
• Subtask 4: 51 / 51