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

문제 설명

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

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

풀이 방법

• 중복 허용 -> N과M(3)번과 유사하다.
• 비내림차순 -> N과M(2)번과 유사하다.
• 즉, 매개변수에 idx를 추가하지만, 오름차순이 아니기 때문에 +1을 넣어주지 않으면 된다.
• idx에 값으로 반복문을 돌기 때문에 arr[0]은 항상 arr[1] 보다 작거나 같게 된다.

알아야되는 개념

• 백트래킹
• Stringbuilder

import java.util.Scanner;

public class Main {
    private static int N,M;
    private static int arr[];
    private static StringBuilder sb = new StringBuilder();
    public static void func(int depth, int N, int M, int idx){
        if (depth == M){
            for(int i=0;i<M;i++){
                sb.append(arr[i] + " ");
            }
            sb.append("\n");
            return;
        }
        else {
            for (int i = idx; i <= N; i++) {
                arr[depth] = i;
                func(depth + 1, N, M, i);
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        arr = new int[10];
        Main.func(0, N, M, 1);
        System.out.print(sb);
    }
}