boj 14620

해결방법

brute force로 3개를 선택하여 최솟값을 구한다.

그리디한 방법으로 풀면 안됨.

#include <iostream> 

#include <iterator>

#include <algorithm> 

#include <vector>

#include <list>

#include <map>

#include <set>

#include <queue>

#include <stack>

#include <string>

#include <cmath>

#include <cstdio>

#include <cstring>

using namespace std;

#define MOD 1000000007

#define INF 2147483647

#define LNF 9223372036854775807

#define pb push_back

#define mp make_pair

typedef long long ll;

typedef unsigned long long ull;

typedef pair<ll,ll> pll;

typedef pair<int,int> pii;

int main(){

freopen("sample.txt","r",stdin);

vector<int> vec;

int n, data[10][10],len,ret=10000;

scanf("%d",&n);

for(int i=0;i<n;i++)

for(int j=0;j<n;j++)

scanf("%d",&data[i][j]);

for(int i=1;i<n-1;i++)

for(int j=1;j<n-1;j++)

vec.pb(data[i][j]+data[i-1][j]+data[i][j-1]+data[i+1][j]+data[i][j+1]);

len = vec.size();

for(int i=0;i<len;i++){

for(int j=i+1;j<len;j++){

for(int k=j+1;k<len;k++){

int xi=i/(n-2),yi=i%(n-2);

int xj=j/(n-2),yj=j%(n-2);

int xk=k/(n-2),yk=k%(n-2);

if(abs(xi-xj)+abs(yi-yj)>2 && abs(xi-xk)+abs(yi-yk)>2 && abs(xj-xk)+abs(yj-yk)>2)

ret = min(ret, vec[i]+vec[j]+vec[k]);

}

}

}

printf("%d\n",ret);

return 0;

}