BOJ 15656 - N과 M (7)

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

15656번: N과 M (7)

 

1. 아이디어

N개의 자연수 중에서 중복을 허용하여 M개를 순서있게 나열하는 중복순열 문제이다.

 

각 자리에서 다음 자리에 올 수 있는 모든 경우의 수를 탐색한다.

 

 

2. 시간복잡도

중복순열 문제이므로 N개 중 M개의 자리를 뽑는 것과 같으므로 시간복잡도는 O(N^M)이다.

 

N과 M의 최댓값은 7이므로 7^7 < 1초라서 가능한 풀이법이다.

 

3. 구현

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M;
    static int[] nums, selected;

    public static void main(String[] args) throws IOException {
        input();

        Arrays.sort(nums);

        rec_func(1);

        bw.close();
    }

    static void rec_func(int k) throws IOException {
        if (k == M + 1) {
            for (int i = 1; i <= M; i++) {
                bw.write(selected[i] + " ");
            }
            bw.write("\n");
        } else {
            for (int i = 1; i <= N; i++) {
                int n = nums[i];

                selected[k] = n;

                rec_func(k + 1);

                selected[k] = 0;
            }
        }
    }

    static void input() 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());

        nums = new int[N + 1];
        selected = new int[M + 1];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
    }
}