#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int A[1002][1002]= { { 0}};
int L[1002][1002]= { { 0}};
int R[1002][1002]= { { 0}};
int D[1002][1002]= { { 0}};
int main()
{
int n;
int i,j;
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d",&n);
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
scanf("%d",&A[i][j]);
}
}
for(i=1; i<=n; i++)
{
L[i][1]=D[i-1][1]+A[i][1]; //1열에 대한 처리
if(i>1) //2행 이후에 대한 처리
{
for(j=2; j<=n; j++)
{
L[i][j]=max(L[i][j-1],D[i-1][j])+A[i][j];
}
}
else //1행에 대한 처리
{
for(j=2; j<=n; j++)
{
L[i][j]=L[i][j-1]+A[i][j];
}
}
//R[1][j]는 초기화된 0 그대로 둠 (A[1][1]부터 시작이므로 역방향은 불가능)
if(i>1)
{
R[i][n]=D[i-1][n]+A[i][n];
for(j=n-1; j>=1; j--)
{
R[i][j]=max(R[i][j+1],D[i-1][j])+A[i][j];
}
}
for(j=1; j<=n; j++)
{
if(i>1)
{
D[i][j]=max(L[i][j],R[i][j]);
}
else
{
D[i][j]=L[i][j];
}
}
}
printf("%d",D[n][n]);
return 0;
}
==================================================
#include <cstdio>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;
typedef struct
{
int height;
int price;
} picture;
bool compare(picture p1, picture p2){
return p1.height < p2.height;
}
int main()
{
time_t start, end;
int N, S, i;
int max=-9999999;
vector<picture> pic;
vector<int> idx;
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d %d",&N,&S);
pic.resize(N);
idx.resize(N);
for(i=0;i<N;i++)
{
scanf("%d %d",&(pic[i].height),&(pic[i].price));
idx[i]=i;
}
// 높이를 기준으로 정렬
// sort(pic.begin(),pic.end(),compare);
// 높이를 기준으로 사전식 순열
start=time(NULL);
do
{
int sum=0;
int lastPicHeight=0;
for(i=0;i<N;i++)
{
if(pic[idx[i]].height>lastPicHeight)
{
if((pic[idx[i]].height-lastPicHeight)>=S)
{
sum+=pic[idx[i]].price;
}
lastPicHeight=pic[idx[i]].height;
}
}
if(max<sum) max=sum;
end=time(NULL);
if(difftime(end,start)>0.98) break;
}while(next_permutation(idx.begin(),idx.end()));
printf("%d",max);
return 0;
}
