[Baekjoon] 15651 - N과 M (3)

📝 문제

 

 

🔑 풀이 과정

· 같은 수를 여러 번 골라도 된다 → 중복 허용, 즉 방문배열이 필요가 없다.

 

 

 

🔓 답안

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

public class Main {

    static StringBuilder sb;

    static int N;
    static int M;

    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[M];

        DFS(0);

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    static void DFS(int depth){
        if(depth == M){
            for(int n : arr)
                sb.append(n).append(" ");
            sb.append("\n");
            return;
        }

        for(int i = 1; i <= N; i++){
            arr[depth] = i;
            DFS(depth + 1);
        }
    }
}

 

 

 

🖤 알고리즘 분류

- 백트래킹