[백준] 15652번 N과 M (4) java

1. 백준 15652번 문제

1.문제

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

1부터 N까지 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
고른 수열은 비내림차순이어야 한다.
길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

2.입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

3.출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

2. 문제 해석

중복을 허용해서 조합할 수 있는 수로 '비내림차순'인 수열을 출력하는 문제입니다.

3. 문제 풀이

import java.util.Scanner;

public class Main {

    public static int N, M;
    public static int[] arr;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        N = in.nextInt(); //자연수 입력받기
        M = in.nextInt(); //깊이 입력받기
        arr = new int[M]; //깊이 만큼 배열 생성

        dfs(1, 0);
    }
    public static void dfs(int at, int depth) {
        //phase1
        if (depth == M) {
            for (int val : arr) {
                System.out.print(val + " ");
            }
            System.out.println();
            return;
        }
        //phase2
        for (int i = at; i <= N; i++) {
            arr[depth] = i; //깊이가 0일때 배열의 첫번째 자리에 1의 값이 대입된다.
            //dfs(i, depth + 1); 깊이가 + 1 되었으므로 다음 배열의 자리에는 1부터 입력이되서 1,2,3 이 차례대로 대입됩니다.
            //그로인해 1,1이 depth가 충족이 된다면 출력이 됩니다. 그게 아닌경우에는 다시 다음 배열자리로 반복문이 1부터 넘어갑니다.
            dfs(i, depth + 1);
        }
    }
}

실행 결과

3
2
1 1 
1 2 
1 3 
2 2 
2 3 
3 3