[백준] 15650번: N과 M (2) (dfs, 백트래킹)

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

15650번: N과 M (2)

 

코드

import java.util.Scanner;

public class Main {
	public static int arr[];
	public static boolean visit[];
	public static int N;
	public static int M;
	public static StringBuilder sb = new StringBuilder();
	
	public static void dfs(int count) {
		if(count == M) {
			for(int i=0; i<M-1; i++) {
				if(arr[i] > arr[i+1])
					return;
			}
			
			for(int i : arr)
				sb.append(i + " ");
			sb.append("\n");
			return;
		}
		
		for(int i=1; i<=N; i++) {
			if(!visit[i]) {
				visit[i] = true;
				arr[count] = i;
				dfs(count+1);
				visit[i] = false;
			}
		}
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();
		M = scan.nextInt();
		arr = new int[M];
		visit = new boolean[N+1];
		dfs(0);
		
		System.out.println(sb);
		scan.close();
	}

}

 

풀이

N과 M (1) 참고

N과 M (1)번 문제와 동일하지만 차이점은,

 ● 고른 수열이 오름차순이어야 한다.

위 하나밖에 없다. 

따라서 M개만큼 순열을 골랐을 때, 고른 순열이 오름차순이 아닐경우 아무런 수행 없이 종료해주고,

오름차순일 경우 StringBuilder 에 저장한다.

if(count == M) {
	for(int i=0; i<M-1; i++) {
		if(arr[i] > arr[i+1])
			return;
	}
					
	for(int i : arr)
		sb.append(i + " ");
	sb.append("\n");
	return;
}