재귀 - 백준 15655 N과 M (6) - 중복 없는 오름차순 조합

N과 M (6) 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

22723

19035

15418

84.408%

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1 복사

3 1
4 5 2

예제 출력 1 복사

2
4
5

예제 입력 2 복사

4 2
9 8 7 1

예제 출력 2 복사

1 7
1 8
1 9
7 8
7 9
8 9

예제 입력 3 복사

4 4
1231 1232 1233 1234

예제 출력 3 복사

1231 1232 1233 1234

 

 

- 중복 없이 주어진 수의 오름차순을 구하는 문제이다. 

- 재귀호출을 이용해서 쉽게 구할 수 있다.

 

풀이

 

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int[] arr;
    static int[] output;
    static boolean[] check;
    static int M;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");

         N = Integer.parseInt(input[0]);
         M = Integer.parseInt(input[1]);

         output = new int[N];
        check = new boolean[N];

        arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        //정렬 -> 사전순으로 출력
        Arrays.sort(arr);
      
        recursiveComb(0,0);
        bw.flush();
        bw.close();
    }
  

    static void recursiveComb(int next, int depth) throws IOException {

        //BASE CASE
        if(depth == M){
            for(int i=0; i<M;i++){
                bw.write(output[i]+" ");
            }
            bw.write("\n");
        }else{

        //RECURSIVE CASE
        //어차피 사전순으로 정렬 1 2 3 4 5 -> 무조건 자신보다 뒤 순서랑 짝지으면 됨
        // 1 3 OK 3 1 X
        //다음으로 선택될 수는 자기 자신보다 앞에 있다
            // 1 -> for문 시작점을 next에 담아서 호출시마다 i+1해준다!
            //
        for(int i=next; i<N;i++){
            if(!check[i]){
                check[i] = true;
                output[depth] = arr[i];
                recursiveComb(i+1,depth+1);
                check[i] = false;
            }
        }


        }


    }


}