Q. 15657 자바 : N과 M(8)

Q. 15657 자바 : N과 M(8)

 

문제 : boj.kr/15657

실버 3 난이도의 문제이다.

 

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

N개의 자연수는 모두 다른 수이다.

 

- N개의 자연수 중에서 M개를 고른 수열

- 같은 수를 여러 번 골라도 된다.

- 고른 수열은 비내림차순이어야 한다.

- 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

 

수열에서 원소를 선택할 때는 중복을 허용하지만, 수열은 중복하면 안된다.주의해야 할 점은 수열은 사전 순으로 증가하는 순서로 출력한다 라는 내용 때문에 수열을 입력 받은 뒤 정렬이 한번 필요하다.

 

이 문제는 백트래킹과 재귀함수를 이용해 풀었고,

이전 계산한 결과를 배열에 저장하고, 깊이가 최대일 때 까지 탐색을 완료하면 저장한 결과를 출력하는 방식으로 풀었다.

앞의 M과N(5) 문제와 유사하지만, 재귀함수를 호출할 때 for문의 인덱스를 받아서

그 인덱스부터 반복을 하고, 수열의 원소는 중복을 허용하므로 그냥 입력을 받으면 된다.

 

시간 복잡도를 어떻게 구할지 감이 안잡혀서 찾아보다 보니,

중복 조합을 구하는 방식을 계산하면 된다는 것을 알았다.

M과 N이 최대 8이므로 8 H 8 = 15 C 8 = 15! / (8! * 7!)으로 계산해보니

약 6435번만 계산하면 계산할 수 있고, 시간 복잡도는 걱정하지 않아도 될 것 이다.

모든 자료형은 int로 해결했고, 다른 방법은 모르겠다.

 

풀이는 아래와 같다.

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

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N, M;
    static int[] input_val;
    static int[] prev_val;

    static void input() {

        N = scan.nextInt();
        M = scan.nextInt();
        input_val = new int[N];
        prev_val = new int[M];
        for (int i = 0; i < N; i++) input_val[i] = scan.nextInt();
    }

    static void pro() {
        Arrays.sort(input_val);
        recur_func(0, 0);
        System.out.println(sb);
    }

    static void recur_func(int depth, int idx) {
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(prev_val[i]).append(' ');
            }
            sb.append('\n');
        }else {
            for (int i = idx; i < N; i++){
                prev_val[depth] = input_val[i];
                recur_func(depth + 1, i);
            }
        }
    }

    public static void main(String[] args) {
        input();
        pro();
    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}