[백준][15651번]N과 M(3)[JAVA]

문제 설명

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

풀이 방법

• N과 M(1)에는 중복을 허용하지 않나 visit 배열을 사용했었다. 하지만 N과M(3)에서는 중복을 허용해준다 !!
• 그럼으로 중복을 체크했던 visit 부분을 지워주면 된다. 단, JAVA를 사용할 경우 System.out.print를 쓰면 시간 초과가 발생한다.
• 이러한 문제를 방지하기 위해서 StringBuilder를 사용하면 된다. (System.out.print는 매우 느린 속도를 갖고 있다)

알아야되는 개념

• 백트래킹
• 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){
        if (depth == M){
            for(int i=0;i<M;i++){
                sb.append(arr[i] + " ");
            }
            sb.append("\n");
            return;
        }
        else {
            for (int i = 1; i <= N; i++) {
                arr[depth] = i;
                func(depth + 1, N, M);
            }
        }
    }
    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);
        System.out.print(sb);
    }
}