[Programmers] PCCP 모의고사 1회 2번 - 체육대회 - Java

문제

프로그래머스

 

풀이

종목에 참여할 수 있는 사람들 중, 종목의 개수만큼 사람들을 뽑아서 종목 번호(인덱스)를 할당하면 되는 문제이다.

1. 사람, 종목의 개수를 기록하고, 종목 인덱스를 기록할 배열(personArr)을 만든다.

2. 재귀를 이용해서, 사람에 해당하는 인덱스에 종목에 대한 인덱스를 기록한다.

3. 종류 개수만큼 다 돌면 합계를 계산해서 최댓값을 갱신한다.

 

소스코드

import java.util.Arrays;

class Solution {
    private static int personCnt;
    private static int kindCnt;
    private static int answer;
    
    private static int[] personArr;
    private static int[][] ability1;
    
    public int solution(int[][] ability) {
        personCnt = ability.length;
        kindCnt = ability[0].length;
        
        ability1 = ability;
        
        personArr = new int[personCnt];
        
        Arrays.fill(personArr, -1);
        
        answer = Integer.MIN_VALUE;
        
        backTrack(0, 0);
        
        return answer;
    }
    
    private static void backTrack(int currentKind, int depth) {
        if (depth == kindCnt) {
            int sum = 0;
            
            for (int i = 0; i < personCnt; i++) {
                if (personArr[i] != -1) {
                    sum += ability1[i][personArr[i]];
                }
            }
            
            answer = Math.max(sum, answer);
            
            return;
        }
        
        for (int i = 0; i < personCnt; i++) {
            if (personArr[i] == -1) {
                personArr[i] = currentKind;
                backTrack(currentKind + 1, depth + 1);
                personArr[i] = -1;
            }   
        }
    }
}

 

실행 결과