[백준] N과 M (4) - 15652

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

 

해당 문제는 수열문제이고 비 내림차순 수열이다. 또한 중복이 가능한 것에 초점을 맞추어 백트래킹으로 풀었다.

 

코드

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

class Main {
    private static int N;
    private static int M;
    private static int[] arr;
    private 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(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[M];

        dfs(1,0);
        System.out.println(sb);
    }

    private static void dfs(int start, int depth) {
        if (depth == M) {
            for (int value : arr) {
                sb.append(value).append(" ");
            }
            sb.append("\n");
            return;
        }

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

    }
}

 

백트래킹은 탈출 조건만 잘 확인하면 되기 때문에 막히는 부분 없이 해결하였다.