[BOJ] 15650: N과 M(2) (JAVA)

15650번: N과 M (2)

 

풀이

 

깊이 depth변수와 수열을 저장해줄 tmp변수를 사용해서 문제를 풀었다.

오름차순이어야 하기 때문에 Comb 메서드에서 새로 뽑아주는 i는 이전에 들어온 x보다 무조건 커야한다.

M개 만큼 뽑았으면 StringBuilder에 담아준다.

 

전체코드

 

package 백준renew;

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

public class 실버3_15650_N과M2 {
	static int N, M;
	static boolean arr[];
	static int depth;
	static String tmp = "";
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws Exception{
		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());
		
		for(int i=1; i<=N; i++) {
			arr = new boolean[N+1];
			depth = 1;
			arr[i] = true;
			tmp = i+" ";
			Comb(i, depth, tmp);
		}
		
		bw.write(sb.toString());
		bw.close();
		
	}
	static void Comb(int x, int depth, String tmp) {
		if(depth == M) {
			sb.append(tmp).append('\n');
		}
		for(int i=1; i<=N; i++) {
			if(x < i && !arr[i]) {
				arr[i] = true;
				Comb(i, depth+1, tmp+i+" ");
				arr[i] = false;
			}
		}
		
	}
}