[JAVA] DFS : Combination(조합) - 예제 문제 풀이(3단계)

 

3단계

[문제]

 

 

N개의 숫자 중 M개를 선택하는 조합을 구한 뒤, 선택한 숫자들의 곱을 최대로 하는 조합을 찾아라.

 

[입력]

N = 4, M = 2
nums = [1, 5, 3, 2]

 

[출력]

5 3

 

[접근 방법] 

1. DFS로 모든 조합을 탐색하면서 arr에 조합을 담고, 매번 곱을 계산
2-1. dfs반복 횟수 (depth가 M번이랑 같을 때) => 곱한 값과 최댓 값을 비교해서 갱신한다.

2-2. 곱을 갱신하면서 최대의 곱한 값을 만든 조합의 수를 ans배열에 복사한다.

 

[코드]

public class Main {
    static int N, M, K;
    static int[] arr;
    static int[] ans;
    static long max = 0;  // 오버플로우 방지를 위해 long 사용
    
    public static void main(String[] args){
        N = 4; M = 2;
        int[] nums = {1, 5, 3, 2};

        arr = new int[M];
        ans = new int[M];
    
        dfs(0, nums, 0, 1L);
        for(int a : ans){
            System.out.print(a + " ");
        }
    }
    
    static void dfs(int idx, int[] nums, int depth, long multi){
        if(depth == M){
             if(max < multi){
                max = multi;
                System.arraycopy(arr, 0, ans, 0, M);  // 배열 복사 최적화
             } 
             return;
        }
        for(int i=idx; i<N; i++){
            arr[depth] = nums[i];
            dfs(i+1, nums, depth+1, multi*nums[i]);
        }
    }
}