[Java] 프로그래머스 PCCP 실전모의고사 - 체육대회

[Java] 프로그래머스 PCCP 실전모의고사 - 체육대회

 

문   제 : 

당신이 다니는 학교는 매년 체육대회를 합니다. 
체육대회는 여러 종목에 대해 각 반의 해당 종목 대표가 1명씩 나와 대결을 하며, 한 학생은 최대 한개의 종목 대표만 할 수 있습니다.
당신의 반에서도 한 종목당 1명의 대표를 뽑으려고 합니다.
학생들마다 각 종목에 대한 능력이 다르지만 이 능력은 수치화되어 있어 미리 알 수 있습니다.
당신의 반의 전략은 각 종목 대표의 해당 종목에 대한 능력치의 합을 최대화하는 것입니다.

당신의 반 학생들의 각 종목에 대한 능력치를 나타내는 2차원 정수 배열 ability가 주어졌을 때, 
선발된 대표들의 해당 종목에 대한 능력치 합의 최대값을 return 하는 solution 함수를 완성하시오.

 

제한사항(Constraint)

• 1 ≤ ability의 행의 길이 = 학생 수 ≤ 10
• 1 ≤ ability의 열의 길이 = 종목 수 ≤ ability의 행의 길이
• 0 ≤ ability[i][j] ≤ 10,000
  • ability[i][j]는 i+1번 학생의 j+1번 종목에 대한 능력치를 의미합니다.

 

 

Example )

Input : [[40, 10, 10], [20, 5, 0], [30, 30, 30], [70, 0, 70], [100, 100, 100]]
Output : 210

Input : [[20, 30], [30, 20], [20, 30]]
Output : 60

---

접   근 : 

 

각 종목에 대한 학생 대표를 뽑는데, 중복이 불가하다.각 행과 열에서 중복되지 않게 원소를 뽑는 경우의 수 -> 순열

 

 

---

결   과  :

import java.util.*;

class Solution {
    public static int result = Integer.MIN_VALUE;
    
    public int solution(int[][] ability) {
        // check 배열을 두고 각 종목을 뽑았는지 남았는지
        // 재귀하면서 각 종목에 나갈수 있는 모든 경우의 수 계산 
        // 순열
        
        int[] check = new int[ability.length]; // 학생이 선택됐는지
    
        solve(ability, check, 0, 0);
        return result;
    }
    
    public void solve(int[][] ability, int[] check, int abil, int depth){
        if(depth == ability[0].length) {
            result = Math.max(result, abil);
            return;
        }
        
        for(int i=0; i<ability.length; i++){
            if(check[i] == 1) // 해당 학생이 이미 대표로 뽑혀있는 경우
                continue; 
            check[i] = 1;
            solve(ability, check, abil+ability[i][depth], depth+1);
            check[i] = 0;
        }
    }
}