1. 오늘의 문제

2. 참가자

  • 15이원준

3. 코드

3.1. 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;
}

3.2. 박인서


3.3. 곽정흠


4. 아이디어

4.1. 15이원준

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

4.2. 박인서


4.3. 곽정흠

Retrieved from http://wiki.zeropage.org/wiki.php/1R/2016_10_09
last modified 2021-02-07 05:22:08