[240502] 알고리즘 리부트 58일차 - 백준 N과 M 시리즈 자바

N과 M 시리즈

N과 M (1)  (각기 다른 수) 1부터 N까지의 수 중 중복 없도록 M개 고른 수열 
N과 M (2)  (각기 다른 수) 1부터 N까지의 수 중 중복 없도록 M개 고르는데 각 원소가 오름차순인 수열 
N과 M (3)  (각기 다른 수) 1부터 N까지의 수 M개 고른 수열(원소 중복 가능) 
N과 M (4)  (각기 다른 수) 1부터 N까지의 수 M개 고르는 데 원소 중복 가능하나 각 원소가 같거나 오름차순인 수열
N과 M (5)  (각기 다른 수) 주어진 수 중 중복 없도록 M개 고른 수열
N과 M (6)  (각기 다른 수) 주어진 수 중 중복 없도록 M개 고르는데 각 원소가 오름차순인 수열
N과 M (7)  (각기 다른 수) 주어진 수 중 M개 고른 수열(원소 중복 가능)
N과 M (8)  (각기 다른 수) 주어진 수 중 M개 고르는 데 원소 중복 가능하나 각 원소가 같거나 오름차순인 수열
N과 M (9)  (동일 숫자 존재) 주어진 수 중 M개 고르는 데 원소 중복 불가, 동일 숫자인 원소는 중복 가능한 수열
N과 M (10)  (동일 숫자 존재) 주어진 수 중 M개 고르는 데 원소 중복 불가, 동일 숫자인 원소는 중복 가능하나 각 원소가 같거나 오름차순인 수열
N과 M (11) (동일 숫자 존재) 주어진 수 중 M개 고른 수열 (동일한 수열은 출력하지 않음)
N과 M (12) (동일 숫자 존재) 주어진 수 중 M개 고르는 데 원소 중복가능하나 각 원소가 같거나 오름차순인 수열(동일한 수열은 출력하지 않음)

 

이 문제를 풀면서 적용한 조건은

1) 방문 배열
2) 동일한 순서에 배정되는 직전에 뽑은 수(이미 뽑은 수열인지 확인)
3) 직전에 뽑은 수(앞 원소)

N과 M (9) 
(동일 숫자 존재) 주어진 수 중 M개 고르는 데 원소 중복 불가, 동일 숫자인 원소는 중복 가능한 수열

package BaekJoon.recursion;

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;

public class BJ15663 {
    public static int n, m;
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static int[] arr;
    public static boolean[] visited;

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

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        arr = new int[n];
        visited = new boolean[n];

        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

        Arrays.sort(arr);

        int[] ans = new int[m];
        getNum(ans, 0);

        bw.flush();

    }

    private static void getNum(int[] ans, int curr) throws IOException {
        if (curr == m) {
            for (int i : ans) bw.write(i + " ");
            bw.write("\n");
            //System.out.println("출력했어");
            return;
        }
        int tmp = 0;
        //System.out.println("tmp는 다시 0");
        for (int i = 0; i < n; i++) {
            //System.out.println("tmp(1): " + tmp); //1 7 9 9

            if (visited[i]) {
                //System.out.println("방문했던 애라서 지나감: " + arr[i]);
                continue;
            }
            if ((tmp == arr[i])) {
                //System.out.println("담았던 애라서 지나감: " + arr[i]);
                continue;
            }

            ans[curr] = arr[i];
            tmp = arr[i];
            //System.out.println("tmp(2): " + tmp);
            visited[i] = true;
            getNum(ans, curr + 1);
            visited[i] = false;
        }


    }

}

N과 M (10) 
(동일 숫자 존재) 주어진 수 중 M개 고르는 데 원소 중복 불가, 동일 숫자인 원소는 중복 가능하나 각 원소가 같거나 오름차순인 수열

package BaekJoon.recursion;

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;

public class BJ15664 {
    public static int n, m;
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static int[] arr;
    public static boolean[] visited;

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

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        arr = new int[n];
        visited = new boolean[n];

        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

        Arrays.sort(arr);

        int[] ans = new int[m];
        getNum(ans, 0);

        bw.flush();

    }

    private static void getNum(int[] ans, int curr) throws IOException {
        if (curr == m) {
            for (int i : ans) bw.write(i + " ");
            bw.write("\n");
            //System.out.println("출력했어");
            return;
        }
        int tmp = 0;
        //System.out.println("tmp는 다시 0");
        for (int i = 0; i < n; i++) {
            //System.out.println("tmp(1): " + tmp); //1 7 9 9

            if (visited[i] || (curr != 0 && ans[curr - 1] > arr[i])) {
                //System.out.println("방문했던 애라서 지나감: " + arr[i]);
                continue;
            }
            if ((tmp == arr[i])) {
                //System.out.println("담았던 애라서 지나감: " + arr[i]);
                continue;
            }

            ans[curr] = arr[i];
            tmp = arr[i];
            //System.out.println("tmp(2): " + tmp);
            visited[i] = true;
            getNum(ans, curr + 1);
            visited[i] = false;
        }


    }


}

N과 M (11)
(동일 숫자 존재) 주어진 수 중 M개 고른 수열 (동일한 수열은 출력하지 않음)

package BaekJoon.recursion;

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;

public class BJ15665 {
    public static int n, m;
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static int[] arr;
    public static boolean[] visited;

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

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        arr = new int[n];
        visited = new boolean[n];

        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

        Arrays.sort(arr);

        int[] ans = new int[m];
        getNum(ans, 0);

        bw.flush();

    }

    private static void getNum(int[] ans, int curr) throws IOException {
        if (curr == m) {
            for (int i : ans) bw.write(i + " ");
            bw.write("\n");
            return;
        }
        int tmp = 0;
        for (int i = 0; i < n; i++) {

            if ((tmp == arr[i])) {
                continue;
            }

            ans[curr] = arr[i];
            tmp = arr[i];
            getNum(ans, curr + 1);
        }


    }


}

N과 M (12) 
(동일 숫자 존재) 주어진 수 중 M개 고르는 데 원소 중복가능하나 각 원소가 같거나 오름차순인 수열(동일한 수열은 출력하지 않음)

package BaekJoon.recursion;

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;

public class BJ15666 {
    public static int n, m;
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static int[] arr;
    public static boolean[] visited;

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

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        arr = new int[n];
        visited = new boolean[n];

        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

        Arrays.sort(arr);

        int[] ans = new int[m];
        getNum(ans, 0);

        bw.flush();

    }

    private static void getNum(int[] ans, int curr) throws IOException {
        if (curr == m) {
            for (int i : ans) bw.write(i + " ");
            bw.write("\n");
            return;
        }
        int tmp = 0;
        for (int i = 0; i < n; i++) {

            if (curr != 0 && ans[curr - 1] > arr[i]) {
                continue;
            }
            if ((tmp == arr[i])) {
                continue;
            }

            ans[curr] = arr[i];
            tmp = arr[i];
            getNum(ans, curr + 1);
        }


    }

}