[알고리즘]15651. N 과 M ( 3 )

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

15651번: N과 M (3)

 

package org.example.N과M3;

import java.io.*;
import java.text.MessageFormat;
import java.util.StringTokenizer;

/**
 * packageName    : org.example.N과M3
 * fileName       : Main
 * author         : ipeac
 * date           : 2023-08-16
 * description    :
 * ===========================================================
 * DATE              AUTHOR             NOTE
 * -----------------------------------------------------------
 * 2023-08-16        ipeac       최초 생성
 */
/*
* 문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.
*  */
public class Main {
    static FastReader fr = new FastReader();
    static FastWriter fw = new FastWriter();
    public static void main(String[] args) {
        int n = fr.nextInt();
        int m = fr.nextInt();
        
        if (!(1 <= m && m <= n && n <= 7)) {
            String messageFormat = MessageFormat.format("1 <= M <= N <= 7, but M = {0}, N = {1}", m, n);
            throw new IllegalArgumentException(messageFormat);
        }
        
        int[] arr = new int[m];
        
        dfs(arr, n, m, 0);
        fw.flush();
        
    }
    
    private static void dfs(int[] arr, int n, int maxLength, int depth) {
        if (depth == maxLength) {
            for (int i : arr) {
                fw.write(i + " ");
            }
            fw.newLine();
            return;
        }
        for (int i = 1; i <= n; i++) {
            arr[depth] = i;
            dfs(arr, n, maxLength, depth + 1);
        }
    }
    
    public static class FastWriter {
        private BufferedWriter bw;
        
        public FastWriter() {
            bw = new BufferedWriter(new OutputStreamWriter(System.out));
        }
        
        public void write(String str) {
            try {
                bw.write(str);
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        
        public void flush() {
            try {
                bw.flush();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        public void newLine() {
            try {
                bw.newLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
    
    public static class FastReader {
        private BufferedReader br;
        private StringTokenizer st;
        
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        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());
        }
        
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}