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

안녕하세요 놀이방 사장입니다.

 

이번 포스팅은 백준 15650

"N과 M(2)" 문제입니다.

 

15650번: N과 M (2)

이 포스팅을 보시기 전에 16549번 N과M(1) 포스팅을 보고 오시면 좋을 거 같습니다.

 

그 코드에서 예외처리만 조금해주면 풀리는 문제이기 떄문입니다.

출력을 보면 아시겠지만

뒤에 출력되는 숫자들이 앞에 숫자보다 커져야합니다.

N과M(1)  코드에서 저 예외처리만 해주면 됩니다.

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

public class Main{
    public static int[] arr;
    public static boolean[] check;
    public static StringBuilder sb = new StringBuilder();

    public static void dfs(int n, int m, int depth){
        if(depth == m){
            for(int i : arr){
                sb.append(i).append(' ');
            }
            sb.append('\n');
            return;
        }

        for(int i=0; i<n; i++){
            if(!check[i]){
                if(depth > 0){
                    if(arr[depth-1] <= i){
                        check[i] = true;
                        arr[depth] = i+1;
                        dfs(n,m,depth+1);
                        check[i] = false;
                    }
                }else{
                    check[i] = true;
                    arr[depth] = i+1;
                    dfs(n,m,depth+1);
                    check[i] = false;
                }


            }
        }
    }

    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        arr = new int[m];
        check = new boolean[n];

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

먼저 첫번쨰 숫자일 떄는 그대로 로직을 태우고 그 뒤로는 앞에 숫자보다 값이 클 떄만 로직을 태워주면 됩니다.

그러면 정답처리되는 문제입니다.

 

앞에 N과M(1)를 이해하셨으면 풀 수 있는 문제입니다.