[BaekJoon] 15650번 N과 M (2) 문제 풀이 (Success)

15650번: N과 M (2)

 

☕Language: Java

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int[] arr;
    public static StringBuilder sb = new StringBuilder();
 
    public static int N, M;
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        arr = new int[M];
        dfs(1, 0);
 
        br.close();
 
        bw.write(sb.toString());
 
        bw.flush();
        bw.close();
 
    }
 
    public static void dfs(int idx, int depth) {
        if (depth == M) {
            for (int val : arr) {
                sb.append(val).append(' ');
            }
            sb.append('\n');
            return;
        }
 
        for (int i = idx; i <= N; i++) {
            arr[depth] = i;
            dfs(i + 1, depth + 1);
 
        }
    }
}
 

🤔 해설

1. for (int i = idx; i <= N; i++) { ... }

    - idx를 함께 이용해 오름차순으로 고른 수열 반환

2. dfs(i + 1, depth + 1);

    - 재귀호출 시, idx를 높여 재방문을 고려하지 않아도 됨

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

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