BOJ_15650 : N과 M (2)

👉 문제링크

15650번: N과 M (2)

---

---

🔸 문제 분석 🔸

• 1부터 n까지의 수 중에 m개를 고르는 경우의 수를 오름차순으로 출력하는 문제이다.
• 재귀문에서 백트래킹조건으로 m개를 고른다.

🔸 코드 🔸

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    private static void dfs(ArrayList<Integer> arr, int n, int m, int i){
        if (arr.size() == m){
            for (int a : arr) {
                System.out.print(a + " ");
            }
            System.out.println("");
        }

        for (int j = i + 1; j <= n; j++) {
            arr.add(j);
            dfs(arr, n, m, j);
            arr.remove(arr.size()-1);
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        ArrayList<Integer> arr = new ArrayList<>();
        dfs(arr,n, m, 0);
    }
}

🔸 코드 해석 🔸

• dfs 메소드에서 재귀로 m개의 수를 고른다.
• 반복문에서 순차적으로 수를 고르기 때문에 오름차순으로 출력된다.

---

🔸 end 🔸

• 이전 N과 M(1)을 푼 직후로 풀어서 어렵지 않게 풀이할 수 있었다.