[Algo] 백준 15650 N과 M(2) JAVA

문제 바로가기 : https://www.acmicpc.net/problem/15650

메모리 : 15864KB

시간 : 148ms

언어 : Java 11

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static boolean[] check;
    static StringBuilder sb = new StringBuilder();
    static int[] ans;

    public static <T> void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        check = new boolean[N + 1];
        dfs(1, 0);
        System.out.print(sb);
    }

    private static void dfs(int idx, int cnt) {
        if (cnt == M) {
            List<Integer> anslist = new ArrayList<>();
            for (int i = 1; i <= N; i++) {
                if (check[i]) {
                    anslist.add(i);
                }
            }
            for (int i : anslist) {
                sb.append(i + " ");
            }
            sb.append("\n");
            return;
        }
        if (idx > N) {
            return;
        }
        check[idx] = true;
        dfs(idx + 1, cnt + 1);
        check[idx] = false;
        dfs(idx + 1, cnt);
    }
}

풀이

1~N까지의 숫자 M개를 골라 정렬하는 문제이다. 조합을 만드는 아주 기초문제!

• check배열은 해당 순서에서 해당 숫자가 선택되었는지를 알려준다.
• cnt는 지금 몇장의 카드가 선택되었는지를 알려준다. cnt==M 일때 선택된 카드를 정렬하면 된다
• 재귀를 이용하면서 카드가 선택되었을때, 선택되지 않았을 때를 모두 확인해보면 된댜.