BOJ 15650 - N과 M(2)

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

---

N과 M (1) 문제와 거의 유사하지만 다른점은 시작하는 숫자보다 작은 숫자는 수열로 올 수 없다는 점이다.

이를 위해 기존과 같이 dfs를 활용하되 매개변수를 하나 더 추가해 범위를 제한시켜 해결하였다.

 

코드는 다음과 같다.

 

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int NUMBER;
    static int LENGTH;
    static boolean[] VISITED;
    static int[] ARR;
    static StringBuilder SB = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        NUMBER = Integer.parseInt(st.nextToken());
        LENGTH = Integer.parseInt(st.nextToken());

        ARR = new int[LENGTH + 1];
        VISITED = new boolean[NUMBER + 1];

        dfs(1, 0);

        System.out.println(SB);
        br.close();
    }

    public static void dfs(int x, int depth) {
        if (depth == LENGTH) {
            for (int i = 0; i < LENGTH; i++) {
                SB.append(ARR[i] + " ");
            }
            SB.append("\n");

            return;
        }

        for (int i = x; i <= NUMBER; i++) {
            if (!VISITED[i]) {
                VISITED[i] = true;
                ARR[depth] = i;
                dfs(i + 1, depth + 1);
                VISITED[i] = false;
            }
        }
    }
}