[BOJ-3980] 선발 명단 -Java

https://www.acmicpc.net/problem/3980

3980번: 선발 명단

package algo;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_3980_선발명단 {
	static int max;
	public static void main(String[] args) throws IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		
		
		int T=Integer.parseInt(br.readLine());
		
		for(int tc=1; tc<=T; tc++) {
			boolean check[]=new boolean[11];
			max=Integer.MIN_VALUE;
			int playerScore[][]=new int[11][11];
			for(int i=0; i<11; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for(int j=0; j<11; j++) {
					playerScore[i][j]=Integer.parseInt(st.nextToken());
				}
			}
			
			solve(check,playerScore, 0, 0);
			System.out.println(max);
			
		}
	}

	private static void solve(boolean [] check, int[][] playerScore, int playerNo, int totalScore) {
		if(playerNo==11) { //11명 다 선정
			max =Math.max(totalScore, max);
			return;
		}
		
		for(int i=0; i<11; i++) {
			if(playerScore[playerNo][i]==0 || check[i]) continue; //능력치 0이면 skip
			check[i]=true;
			solve(check, playerScore, playerNo+1, totalScore+playerScore[playerNo][i]);
			check[i]=false;
		}
		
	}

}

소요시간 : 11분

 

우선 백트래킹 문제입니다!

 

boolean형 배열을 통해서 현재 포지션이 선택되었는지 안되었는지를 확인했습니다.

그리고 현재 선수가 포지션에서의 점수가 0점이거나 , 이미 선택된 포지션이라면 skip해줬습니다.

위의 조건에 걸리지 않는다면 현재 선수를 포지션에 고정시키고 점수를 더해줍니다.

 

그리고 백트래킹을 위해서 solve()함수가 끝나면 바로밑에서 check[i]=false; 를 통해서 선택한 포지션을 없애주었습니다

 

끝~