문제

문제링크

접근

• 우선 문제에서 주어진 값들의 최대 크기가 11 안팍으로 작다. 그래서 완전탐색임을 유추하였다.
• 완전탐색 및 중복조합을 dfs로 구현하였고 주어진 보기 4개도 모두 올바르게 출력하였다.
• 불필요한 탐색은 최대한 없애자!
• 예를 들어 for (int i = point; i < 11; i++) 과 같이 시작점을 유의하여 설정하기!
• 그런데 8번, 18번에서만 계속 틀렸다고 나왔다.
  
• 위와 같은 결과를 가지고 있는 사람은 질문글 이 글을 한 번 보도록 하자!
• 그래서 최대값 갱신하는 코드 (아래 소스에선 //최대값 갱신하기 주석 아래 코드)를 수정하여 100점으로 다시 통과할 수 있게 되었다.

소스코드

// 20220809
package extra.level2;

class Main {
    static int N, M;
    static int[] Group;

    public static void main(String[] args) throws Exception {
        int n = 5;
        int info[] = {2,1,1,1,0,0,0,0,0,0,0};

        Solution sol = new Solution();
        System.out.println("result : " + sol.solution(n, info)[0] + sol.solution(n, info)[1] + sol.solution(n, info)[2]);
    }
}

class Solution {
    int maxGap = -1;
    int n = -1;
    int aInfo[] = new int[11];
    int rInfo[] = new int[11];

    public int[] solution(int n1, int[] info) {
        n = n1;
        aInfo = info.clone();

        int tmp[] = {0,0,0,0,0,0,0,0,0,0,0};
        int tmp2[] = {-1};
        dfs(0, 0, tmp);

        return maxGap == -1 ? tmp2 : rInfo;
    }

    public void dfs(int degree, int point, int[] currInfo) {
        if (degree != 0) currInfo[point]++;
        if (degree == n) {
            int aScore = 0;
            int rScore = 0;

            // 비교
            for (int i = 0; i < 11; i++) {
                if (currInfo[i] == 0 && aInfo[i] == 0)
                    continue;
                else if (currInfo[i] > aInfo[i]) {
                    rScore += (10 - i);
                }
                else {
                    aScore += (10 - i);
                }
            }

            // 최대값 갱신하기
            int currGap = rScore - aScore;
            if ( currGap > 0 &&currGap > maxGap) {
                maxGap = currGap;
                rInfo = currInfo.clone();
            } else if (currGap > 0 && currGap == maxGap) {
                for (int i = 10; i >= 0; i--) {
                    if (currInfo[i] > rInfo[i]) {
                        maxGap = currGap;
                        rInfo = currInfo.clone();
                    } else if (rInfo[i] > currInfo[i]) {
                        return;
                    }
                }
            }

            return;
        } else {
            for (int i = point; i < 11; i++) {

                dfs(degree + 1, i, currInfo.clone());
            }
        }
    }
}