[백준] 15651번 N과 M (3)(JAVA)

Have to know Backtracking

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

15651번: N과 M (3)

위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 13단계

 

백트래킹의 카테고리에 포함되어 있는 문제이다.

 

이전문제들에서는 숫자의 중복이 허용되지 않았다면

 

이번문제는 숫자의 중복이 허용되는 문제이다.

 

자바의 경우 System.out.print를 사용하면 시간초과가 난다.

 

그래서 처음 풀었을 때는 시간초과가 났었다.

 

BufferedWriter를 사용했다.

 

숫자의 중복이 허용됨으로 방문의 표시인 boolean배열은 선언하지 않았다.

 

10번 째 줄에서 bw.write(Output[i]);로 썼을 때, 값들이 아스키 코드값으로 출력된다.

 

그래서 bw.write(String.valueOf(Output[i]));로 변경하였다.

 

이제 그나마 백트래킹의 개념이 이해가 가기 시작하지만 그래도 아직까지 쉽지는 않다.

 

반복과 꾸준한 문제풀이를 통해 완벽하게 이해하도록 노력해야겠다.

 

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

public class Question_15651 {
	static int[] Output = new int[10];
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static void Backtracking(int index, int N, int M) throws IOException {
		if(index == M) {
			for(int i = 0; i < M; i++) {
				bw.write(String.valueOf(Output[i]));
				if(i != M-1)
					bw.write(' ');
			}
			bw.write("\n");
			return;
		}
		
		for(int i = 1; i <= N; i++) {
			Output[index] = i;
			Backtracking(index + 1, N, M);
		}
	}
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		Backtracking(0, N, M);
		bw.flush();
		bw.close();
	}
}