백준 18290 NM과 K (1)

문제 URL : https://www.acmicpc.net/problem/18290

 

문제접근법 :  전수조사로 풀으셔도 됩니다. 

계산해보니 최대1억이라 1억나오게끔 풀려했는데

수학적으로 한칸식 뛰어서 하는게 저한텐 더 코딩이 더쉽더군요

숫자를 이용해서 m으로 나눈몫과 나머지가 y,x좌표가 되니까

x좌표가 m-1좌표면 한칸뛰면되고 왜냐? y좌표가 변하니까

아니면 두칸 뛰면됩니다.

 

소스코드:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<vector<ll>>board,check;
ll n,m,k;
ll res = -1e15;
void input(){
    cin>>n>>m>>k;
    check= board = vector<vector<ll>>(n,vector<ll>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>board[i][j];
        }
    }
}


void dfs(int cnt=0,int sel=k,ll sum=0){
    if(sel==0){
        res= max(res,sum);
        return;
    }
    if(cnt>=n*m){
        return;
    }
    int y= cnt/m;
    int x= cnt%m;
    if(cnt<m){
        check[y][x]=1;
        if(x==m-1)
            dfs(cnt+1,sel-1,sum+board[y][x]);
        else
            dfs(cnt+2,sel-1,sum+board[y][x]);
        check[y][x]=0;
    }
    else{
        if(!check[y-1][x]){    
            check[y][x]=1;
            if(x==m-1)
                dfs(cnt+1,sel-1,sum+board[y][x]);
            else
                dfs(cnt+2,sel-1,sum+board[y][x]);
            check[y][x]=0;
        }
    }
    dfs(cnt+1,sel,sum);
}
void solve(){   
    dfs();
    cout<<res<<"\n";    
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    input();
    solve();
    
   
}

 

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.