백준 15657번 : N과 M (8) java

이 문제는 입력을 받은 후 정렬하고 dfs를 이용하여 조건에 맞게 출력하는 문제입니다.

예제 2번을 예시로 그림을 통해 이 문제를 설명해드리도록 하겠습니다.

위의 그림은 예제 2번에 맞게 N크기의 배열과 M 크기의 배열을 만들었습니다.

M 배열에 들어있는 자료들이 출력될 값입니다.

위 그림과 같이 M배열의 첫 번째에 들어갈 자료는 초록색 박스로 두 번째에 들어갈 자료는 빨간색 박스로 표시하였습니다.

이제 출력이 어떻게 되는지 계속해서 보여드리겠습니다.

초록색 박스가 N배열의 첫번째 칸을 가리킬 때는 이렇게 진행이 됩니다.

이제 초록색 박스를 N배열의 두 번째 칸으로 옮겨보겠습니다.

그럼 위의 그림과 같이 초록색 박스가 시작되는 지점부터 빨간색 박스도 시작합니다.

계속 진행시켜보도록 하겠습니다.

초록색 박스가 세번째 칸으로 넘어가도 위와 같이 진행됩니다.

이제 이 문제에 대한 코드를 보여드리도록 하겠습니다.

---

import java.io.*;
import java.util.*;

public class Main {
    static int[] map;
    static int N, M;
    static int[] answer;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N];
        answer = new int[M];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++)
            map[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(map);

        dfs(0, 0);
    }

    static void dfs(int idx, int count){
        if(count == M){
            for(int i = 0; i<M; i++)
                System.out.print(answer[i]+" ");
            System.out.println();

            return;
        }

        for(int i = idx; i<N; i++){
            answer[count] = map[i];
            dfs(i,count+1);
        }
    }
}

위의 알고리즘과 같이 문제를 해결하였습니다.