[BOJ 15650 N과 M(2)]

N과M(2)

> 문제 풀이

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열. 오름차순으로 출력해야 한다.
N과 M(1)과 다른 점은 고른 수열을 오름차순으로 출력 해야 하기 때문에 중복되는 수열이 존재한다는 것이다. 오름차순으로 출력 해야 하는 부분은 바로 전 숫자와 비교하는 int형 변수 com을 추가하여 문제를 해결했다. N과 M(1)을 기준으로 자신이 짠 재귀 함수를 잘 이해하고 있다면 어렵지 않은 문제이다.

> 프로그램 코드(java)

package 여름방학;

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

public class BOJ15650_N과M2 {
	static int N, M;
	static boolean[] visited;
	static int[] a; // 실제 출력값을 담을 배열

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] temp = br.readLine().split(" ");// temp에 " "을 기준으로 String을 나눠 담음.
		N = Integer.parseInt(temp[0]); // String을 int로 변환 후 담음.
		M = Integer.parseInt(temp[1]);

		visited = new boolean[N + 1];
		a = new int[N + 1];
		dfs(1, 1);
	}

	static void dfs(int depth, int com) {
		if (depth == M + 1) {// 종료 지점
			for (int i = 1; i <= M; i++) {
				System.out.print(a[i] + " ");
			}
			System.out.println();
			return;
		}

		for (int i = 1; i <= N; i++) {
			if (!visited[i] && com <= i) {
				visited[i] = true;
				a[depth] = i;
				dfs(depth + 1, i);
				visited[i] = false;
			}
		}
	}
}