[ 백준 15651 JAVA ] N과 M (3) (Feat. 백트래킹)

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

15651번: N과 M (3)

 

중복을 허용하는 순열 

 

SOLVE

 

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 n과m3 {
	static int N, M;
	static int[] result;
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		result = new int[M];
		DFS(0);
		
		bw.flush(); bw.close();
	}// main end

	public static void DFS(int depth) throws IOException {
		if (depth == M) {
			for (int a : result)
				bw.write(a + " ");
			bw.newLine();
			return;
		} // 기저파트 end

		for (int i = 0; i < N; i++) {
			result[depth] = i + 1;
			DFS(depth+1);
		}
	}// method end
}

 

시간 초과가 발생해서 bw를 사용.

 

중복값을 허용하는 순열문제이다. 

순열 구현에서는 boolean 배열을 사용해 중복된 값을 피한다. 

그러면 boolean 배열을 사용하지 않으면 중복도 허용해서 값을 나열할 것이라고 생각했다. 

따라서 일반적인 중복을 허용하지 않는 순열 구현 코드에서 boolean 부분만 삭제했다.