백준 15650번 - N과 M (2) - (Java 8)

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

15650번: N과 M (2)

 

재귀 + 백트래킹 - BufferedReader + StringBuilder

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
 * @see <a href="https://st-lab.tistory.com/115">st-lab 백준 15650</a>
 */
public class Main {
    static int N;
    static int M;
    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());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[M];
        dfs(0,0);
        System.out.println(sb);
    }
    public static void dfs(int depth, int start){

        if(depth == M){
            for(int num : arr){
                sb.append(num).append(' ');
            }
            sb.append('\n');
            return;
        }

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

depth+1, start+1하면서 재귀 호출한다.

M개만큼 arr에 저장되어야 StringBuilder에 append되고, 그렇지 않으면 for문에서 N값을 넘어가 증발한다.

 

참고해서 풀었다. 사실상 코드를 배꼈다.

https://st-lab.tistory.com/115

[백준] 15650번 : N과 M (2) - JAVA [자바]

 

BufferedWriter + BufferedReader 속도는 백준에선 둘다 76 나왔다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int M;
    static int[] arr;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    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(0,0);
        bw.flush();
        bw.close();
    }
    public static void dfs(int depth, int start) throws IOException {

        if(depth == M){
            for(int num : arr){
                bw.write(num+" ");
            }
            bw.write("\n");
            return;
        }

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