#18290번 NM과 K (1) (C++)

문제 링크 : www.acmicpc.net/problem/18290

18290번: NM과 K (1)

전형적인 Brute Force문제.

어려운 포인트는 딱이 없었으나, 문제를 대충 읽은 탓에 몇 차례 실수를 겪었다.

입력값은 -10000부터 가능하므로, 정답이 무조건 양수만 나온다는 보장이 없다.

때문에 정답의 초기값을 가장 작은 음수로 설정했어야하는데, 별 생각없이 0으로 설정하는 바람에 몇 차례 틀리고 말았다.

 

#include <iostream>
#include <algorithm>
const int MAX = 11;
using namespace std;

int arr[MAX][MAX] = {0,}, ans = -1e4, n = 0, m = 0, k = 0;
bool ch[MAX][MAX] = {false,};
pair<int,int> q[MAX];

bool judge(int y, int x, int cnt){
    for(int i=1; i<=cnt; i++){
        if(q[i].first+1==y&&q[i].second==x) return false;
        if(q[i].first-1==y&&q[i].second==x) return false;
        if(q[i].first==y&&q[i].second+1==x) return false;
        if(q[i].first==y&&q[i].second-1==x) return false;
    }
    return true;
}

void go(int cnt, int sum){
    if(cnt==k){
        if(ans<sum) ans = sum;
        return;
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(!ch[i][j]&&judge(i,j,cnt)){
                ch[i][j] = true;
                q[cnt+1] = {i,j};
                go(cnt+1,sum+arr[i][j]);
                ch[i][j] = false;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m >> k;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> arr[i][j];
        }
    }
    go(0,0);
    cout << ans << "\n";
    return 0;
}

참고로 위 코드는 채점시 824ms가 소요되었다.