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

 

dfs를 이용하여 푸는 문제이다. 처음 접근은 콤비네이션 연산만큼의 결과 값이 나와서 이를 이용하여 풀려고 했는데 잘못된 방법임을 깨닫고 dfs로 풀어서 시간이 오래걸렸다. dfs로 출력의 앞에 나오는 숫자를 지정해주고, depth를 높혀가면서 M과 depth가 같았을 때 저장해두던 배열의 값을 출력하도록 하였다.

 

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

public class p15650 {
	public static int a;
	public static int b;
	public static int[] ary;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		a = Integer.parseInt(st.nextToken());
		b = Integer.parseInt(st.nextToken());
		ary = new int[b];
		dfs(1, 0);

	}

	public static void dfs(int n, int depth) {
		if (depth == b) {
			for (int i = 0; i < ary.length; i++) {
				System.out.print(ary[i] + " ");
			}
			System.out.println();
			return;
		}

		for (int i = n; i <= a; i++) {
			ary[depth] = i;
			dfs(i + 1, depth + 1);
		}
	}
}