PCCP 모의고사 1회 : 체육대회

 

문제 분석

 

종목마다 체육대회 대표를 뽑아서  능력치 합을 최대로 높게만드는 문제다.

 

어떤 알고리즘을 쓸까 고민하다가 역시 DFS,BFS 완전탐색뿐인것 같았다.

 

선수들은 중복으로 대표를 선정할수없으니,  Visited배열로  사용여부를 체크해주자.

 

그 뒤, DFS를 사용해 백트래킹 로직을 짜면 되는 쉬운문제다.

 

문제풀이

 

 

 

import java.util.*;
class Solution {
    
boolean[] visited;
int scope;
int total=0;
    
    public int solution(int[][] ability) {
        //유저수
        visited=new boolean[ability.length];
        //종목수
        scope=ability[0].length;
        
        dfs(ability,0,0);       
        return total;
    }
    
    public void dfs(int[][] ability,int start,int sum){
        
        if(start==scope){
            total=Math.max(total,sum);
            return;
        }
        
        for(int i=0;i<ability.length;i++){
            if(!visited[i]){
                visited[i]=true;
                dfs(ability,start+1,sum+ability[i][start]);
                visited[i]=false;
            }          
        }
    }
}