[PCCP 모의고사 1회] #2 - 체육대회

문제 접근

이 문제는 모든 케이스를 확인해서 결과를 도출해야하는 완전 탐색 문제이다.

	테니스	탁구	수영
석환	40	10	10
영재	20	5	0
인용	30	30	30
정현	70	0	70
준모	100	100	100

재귀함수를 통해 DFS로 최대값을 비교해가며 마지막 케이스까지 검증 후 결과를 리턴한다.

 

 

코드

import java.lang.Math;

class Solution {
    int maxValue = Integer.MIN_VALUE;
    int sum = 0;
    boolean[] visited;
    
    public int solution(int[][] ability) {
        visited = new boolean[ability.length];
        process(ability, 0);
        
        return maxValue;
    }
    
    private void process(int[][] ability, int abilityIndex) {
        // 종목 수만큼 다 조회했을 때 최대값과 비교
        if (abilityIndex == ability[0].length) {
            maxValue = Math.max(maxValue, sum);
        } else {
            for (int i=0; i<ability.length; i++) {
                // 아직 종목 후보로 이름을 넣지 않은 경우 실행
                if (!visited[i]) {
                    visited[i] = true;
                    sum += ability[i][abilityIndex];
                    process(ability, abilityIndex+1);
                    sum -= ability[i][abilityIndex];
                    visited[i] = false;
                }
            }
        }
    }
}

process 메서드에서 for문이 진행될 때 변수 값들을 표로 정리하면,

	테니스(0)	탁구(1)	수영(2)	종목 후보 배열(visited)	총합
i=0	석환			[true, false, false, false, false]	40
i=1	석환	영재		[true, true, false, false, false]	40 + 5
i=2	석환	영재	인용	[true, true, true, false, false]	40 + 5 + 30 (최대값 비교)
i=1	석환	영재		[true, true, false, false, false]	40 + 5 + 30 - 30
i=2	석환	영재	정현	[true, true, false, true, false]	40 + 5 + 70 (최대값 비교)
...	...	...	...	...	...

종목 index 값인 abilityIndex가 3일 때마다 최대값을 비교 후 교체하는 식으로 진행된다.

 

 

보완할 점

1. 완전 탐색을 통해야만 값을 구할 수 있는지?  순회없이 답을 구할 수 있는 방법이 없는지 다음에 다시 한번 풀어보자.

 

문제 링크

https://school.programmers.co.kr/learn/courses/15008/lessons/121684

프로그래머스