BOJ 15657 - N과 M (8)

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

15657번: N과 M (8)

 

1. 아이디어

N개의 자연수 중에서 중복을 허용하여 M개를 골라야 하고 비내림차순이어야 한다.

 

각 자리에서 백트래킹으로 모든 경우의 수를 탐색하는 완전탐색 문제이다.

그 중 중복을 허용하여 순서있게 고르는 것이므로 중복순열 문제이다.

 

재귀함수의 매개변수로 prev를 넘겨줘서 각 경우의 prev에 해당하는 숫자부터 탐색을 시작하도록 설정하면

(k자리의 숫자) <= (k+1자리의 숫자) 가 성립되어서 비내림차순을 만족시킬 수 있다.

2. 시간복잡도

중복순열 문제이므로 O(N^M)이다.

N과 M의 최댓값은 8이므로 8^8 < 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, 1);

        bw.close();
    }

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

                selected[k] = n;

                rec_func(k + 1, i);

                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());
        }
    }
}