[백준 28447] 마라탕 재료 고르기 [Java]

문제

28447번: 마라탕 재료 고르기

28447번: 마라탕 재료 고르기

 

---

풀이

N개 중 K개의 재료를 고르고, K개의 재료들에 대한 맛 궁합을 합한 최댓값을 구하는 문제다.

우선 N개중 K개를 고르는 조합combination을 만들자

    private static void combination(int idx, int depth) {
        if (depth == K) {
            res = Math.max(res, subCombination(0, 0, new int[2]));
            return;
        }
        for (int i = idx; i < N; ++i) {
            if (!visited[i]) {
                visited[i] = true;
                combination(i + 1, depth + 1);
                visited[i] = false;
            }
        }
    }

이제 K개중 2개를 고르는 조합 subCombination을 구현하자. 2개를 골랐다면, 재료의 궁합을 다 합친 후 combination으로 반환해서 최댓값을 비교하면 된다.

    private static int subCombination(int idx, int depth, int[] select) {
        if (depth == 2) {
            return C[select[0]][select[1]];
        }
        int sum = 0;
        for (int i = idx; i < N; i++) {
            if (visited[i]) {
                select[depth] = i;
                sum += subCombination(i + 1, depth + 1, select);
            }
        }
        return sum;
    }

만약 K가 1이라면 재료를 한 개만 고르는 경우이므로 궁합은 0이된다.

        // Solve
        if (K == 1) {
            res = 0;
        } else {
            visited = new boolean[N];
            combination(0, 0);
        }

        // Output
        System.out.println(res);
    }
}

풀이 시간

30분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/28447.java

problem-solving/baekjoon-online-judge/easy/28447.java at main · rogi-rogi/problem-solving