[JAVA] 백준 15650번

[JAVA] 백준 15650번 - N과 M (2)

 

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 Main {

	static BufferedReader br;
	static BufferedWriter bw;
	static int N, M;
	static boolean[] isUsed;
	static int[] answer;

	public static void main(String[] args) throws IOException {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken()); // 1 ~ N 자연수 중
		M = Integer.parseInt(st.nextToken()); // 중복없이 M개 고르기
		answer = new int[M]; // 정답을 담아둘 배열

		isUsed = new boolean[N + 1]; // 해당 숫자가 사용되었는지 확인하기 위한 배열
										// 숫자가 사용된 경우 true, 미사용된 경우 false
		int depth = 0; // 수열의 길이
		int startSearchIdx = 1;	//탐색을 시작할 숫자
		solution(startSearchIdx, depth);

		bw.flush();
		bw.close();

	}

	private static void solution(int startSearchIdx, int depth) throws IOException {
		if (depth == M) { // 수열의 길이가 M과 같다면 출력함
			for (int i = 0; i < answer.length; i++) {
				bw.write(answer[i] + " ");
			}
			bw.newLine();
			return;
		}

		for (int i = startSearchIdx; i <= N; i++) {
			if (isUsed[i] == false) {
				isUsed[i] = true;
				answer[depth] = i;
				solution(i + 1, depth + 1);
				isUsed[i] = false;
			}
		}

	}
}

백준 백트래킹 2번째 문제

 

정답을 맞춘 풀이방법

1. 15649번 : N과 M (1) 문제와 풀이는 거의 유사함

2. 뒤에오는 수열의 숫자가 앞자리의 숫자보다 커야하므로 startSearchIdx 값으로 탐색을 시작할 숫자를 지정함

3. 수열의 길이가 M과 같아진다면 출력