[백준] 15666 : N과 M(12) (JAVA)

https://www.acmicpc.net/problem/15666

 

[풀이과정]

중복되는 부분을 어떻게 해결해야 하는지 고민하다가 시간이 오래 걸렸음.

DFS로 재귀호출 시에 for문 시작 index를 이전 DFS와 같게 하되 배열[index]의 값이 다른 경우에만 값을 sb에 넣게 했다.

이렇게 해야 중복 없는 수열이 나옴.

 

[코드]

import java.util.*;
import java.lang.*;
import java.io.*;
/*
N개 중 M개 고르기
중복 가능
오름차순
*/
class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    static int N, M;
    static int[] A;
    static int[] selected;
    
    public static void main(String[] args) throws IOException{
         init();
        /*
        [출력]
        한 줄에 하나씩 수열 출력. 중복 수열은 한 번만 출력.
        */
        DFS(0,0);
        System.out.print(sb);
    }

    public static void init() throws IOException{
        /*
        [입력]
        1. N, M (1<=M,N<=8)
        2. N개의 수 (1<=크기<=10,000)
        */
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        A = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int n = 0; n < N; n++){
            A[n] = Integer.parseInt(st.nextToken());
        }

        //오름차순 정렬
        Arrays.sort(A);
        selected = new int[M];
    }

    public static void DFS(int start, int depth){
        if(depth == M){
            for(int m = 0; m < M; m++){
                sb.append(selected[m]).append(" ");
            }
            sb.append('\n');
            return;
        }

        int prevNum = -1;
        for(int i = start; i < N; i++){
            if(prevNum != A[i]){
                selected[depth] = A[i];
                prevNum = A[i];
                DFS(i, depth+1);
            }
        }
    }
}