1R/2016 10 09

오늘의 문제

• 교환

참가자

• 15이원준

코드

15이원준

#include<iostream>
#include<algorithm>
using namespace std;

int arr[15][15] = {0,};
int dp[15][10][1<<15] = {0,};
int N;

int dfs(int num,int val, int visited){
  if(dp[num][val][visited]){
    if(dp[num][val][visited] == -1){
      return 0;
    }
    return dp[num][val][visited];
  }
  int maxn = 0;
  for(int i = 0; i<N; i++){
    if(!(visited & (1<<i)) && arr[num][i] >= val){
      maxn = max(maxn, dfs(i, arr[num][i], visited + (1<<i)) + 1);
    }
  }

  dp[num][val][visited] = maxn;
  if(dp[num][val][visited] == 0){
    dp[num][val][visited] = -1;
    return 0;
  }
  return dp[num][val][visited];
}

int main(){
  cin>>N;
  for(int i = 0; i<N; i++){
    for(int j = 0; j<N; j++){
        scanf("%1d", &arr[i][j]);
    }
  }
  cout<<dfs(0,0,1) + 1<<endl;
}

아이디어

15이원준

*dfs로 최대값을 찾고 도중에 겹치는 것은 dp를 이용했습니다.