[백준, Java] 17240번, Team Selection, (그리드)

문제 링크

17240번: Team Selection

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. PPC라는 게임은 5가지 역할군이 존재하며, 5명의 팀으로 이루어집니다.

2. 후보자마다 각 역할군에 대한 실력이 존재합니다.

3. 5명의 역할군으로 팀을 이루었을 때 실력의 합이 최대가 되는 값을 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 각 실력별 정렬한 뒤, 조합을 통해서 최대 실력의 합을 탐색합니다.

 

3. 탐색을 통해 얻은 실력의 최대 합을 결과로 출력합니다.

 

각 실력별 정렬

 

N명의 후보자가 주어졌을 때 각 역할군에 대한 실력을 기준으로 내림차순 정렬을 진행합니다.

 

→ 각 역할군에 높은 실력을 가지고 있는 후보자를 선출하기 위해서입니다.

 

후보자 조합 구하기.

 

후보자에 대한 조합을 구할 때에는 각 역할군에 상위 5명의 후보자를 기준으로 구하면 됩니다.

 

→ 해당 후보자의 조합으로 항상 최대 값이 나오기 때문입니다.

 

Why??

 

5명인 이유는 실력의 최대 합이 되려면 각 역할군에 대한 실력이 높은 사람들을 기준으로 조합을 만들어야 합니다.

 

5명의 조합을 만드는 것으로 최대 5번째 역할군에 있는 후보자까지만 해당 조합에 포함될 수 있습니다.

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 6

 

[후보자]

 

	A	B	C	D	E
후보자1	10	0	0	0	0
후보자2	0	10	0	0	0
후보자3	0	0	10	0	0
후보자4	0	0	0	10	0
후보자5	0	0	0	0	10
후보자6	9	9	9	9	9

 

2. 각 실력별 정렬한 뒤, 조합을 통해서 최대 실력의 합을 탐색합니다.

 

 

[각 실력별 정렬]

 

 

(실력, 후보자 번호)

 

A : { (10, 1), (9, 6), (0, 2), (0, 3) , (0, 4) , (0, 5) }

 

B : { (10, 2), (9, 6), (0, 1), (0, 3) , (0, 4) , (0, 5) }

 

C : { (10, 3), (9, 6), (0, 1), (0, 2) , (0, 4) , (0, 5) }

 

D : { (10, 4), (9, 6), (0,1), (0, 2) , (0, 3) , (0, 5) }

 

E : { (10, 5), (9, 6), (0, 1), (0, 2) , (0, 3) , (0, 4) }

 

 

[각 역할군 상위 5개 기준 조합 진행]

 

A : (10, 1), B :  (10, 2),  C : (10, 3) , D :  (10, 4) ,  E :  (10, 5)

 

총 실력의 합 : 50

 

A :  (9, 6), B : (10, 2),  C : (10, 3) , D : (10, 4) ,  E : (10, 5)

 

총 실력의 합 : 49

 

....

 

3. 탐색을 통해 얻은 실력의 최대 합을 결과로 출력합니다.

 

A :  (10, 1), B : (10, 2),  C : (10, 3) , D : (10, 4) ,  E : (10, 5)

 

최대 실력의 합 : 50

 

 

50 결과로 출력합니다.

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 각 역할군의 실력을 띄어쓰기 기준 나누었습니다.
• Arrrays.sort()을 이용해서 역할 실력 기준 내림차순 정렬을 진행하였습니다.
• 각 역할군 상위 5명을 기준으로 조합을 만드는 search함수를 진행합니다.
• 조합을 통해 얻은 실력의 최대합을 Bufferedwriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 각 상위 5위에 역할군을 기준으로 조합을 진행합니다.
• search함수는 조합으로 얻은 최대 실력의 합을 비교합니다.

결과코드

import java.io.*;
import java.util.*;

public class Main {
    //역할군 실력 정보 관련 클래스
    static class Ability implements Comparable<Ability>{
        //idx : 후보자 번호, stats : 실력
        int idx, stats;
        public Ability(int idx, int stats){
            this.idx = idx;
            this.stats = stats;
        }
        //실력 기준 내림차순 정렬
        @Override
        public int compareTo(Ability ability) {
            return ability.stats - this.stats;
        }
    }
    static int result = 0;
    static Ability[][] abilities;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        abilities = new Ability[5][N];
        //입력되는 후보자 정보 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<5;j++){
                abilities[j][i] = new Ability(i, Integer.parseInt(st.nextToken()));
            }
        }
        //각 역할군 실력 기준 내림차순 정렬
        for(int i=0;i<5;i++){
            Arrays.sort(abilities[i]);
        }
        //후보자 참여 여부 확인 배열
        visited = new boolean[N];
        //상위 5위 각 역할군 조합 탐색
        search(0, 0);
        //최대 실력의 합 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //상위 5위 역할군에 대해서 조합을 진행하여 최대 실력합을 찾는 함수
    static void search(int sum, int idx){
        //5개의 역할군으로 팀이 이루어졌을 때
        if(idx == 5){
            result = Math.max(result, sum);
            return;
        }
        //다음 역할군 탐색
        for(int i=0;i<5;i++){
            Ability cur = abilities[idx][i];
            //현재 팀에 속하지 않은 후보자일 때
            if(!visited[cur.idx]){
                visited[cur.idx] = true;
                search(sum + cur.stats, idx+1);
                visited[cur.idx] = false;
            }
        }
    }
}