백준 15650번 자바 문제 답/해설(N과 M (2) 문제)

[1] 백준 카테고리
단계별로 풀어보기
백트래킹

2단계 N과 M (2)

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

15650번: N과 M (2)

[2] 문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다.

1. 입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

2. 출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.

3. 예제 입력 1
3 1

4. 예제 출력 1
1

2

3

[3] 정답
1. 정답 해설 미포함

import java.io.*;
import java.util.StringTokenizer;
public class Main {
	static int a, b;
	static int[] arr;
	static boolean[] check;
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int index = 1;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		a = Integer.parseInt(st.nextToken());
		b = Integer.parseInt(st.nextToken());
		arr = new int[b];
		check = new boolean[a + 1];
		
		bta(0);
		bw.flush();
		bw.close();
	}

	public static void bta(int index) throws IOException {
		if (index == b) {
			for (int i = 0; i < b; i++) {
				bw.write(arr[i] + " "); 
				}
				bw.write("\n");
				return;
		}

				for (int i = 1; i <= a; i++) {
					if(!check[i]) {
						arr[index] = i;
						check[i] = true;
						bta(index + 1);
						for (int j = i + 1; j <= a; j++)
						{
						check[j] = false;
 						}
					}
				}
	}
}

2.정답 해설 포함

import java.io.*;
// java.io.* 클래스를 import 한다.
import java.util.StringTokenizer;
// java.util.StringToeknizer 클래스를 import 한다.
public class Main {
// 접근제어자 public으로 Main 클래스를 선언한다.
	static int a, b;
	// 메모리에 상주하게 int형 변수 a와 b를 선언한다.
	static int[] arr;
	// 메모리에 상주하게 int형 배열 arr를 길이를 정하지 않고 선언한다.
	static boolean[] check;
	// 메모리에 상주하게 boolean형 배열 check를 선언한다.
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	// 메모리에 상주하게 BufferedWriter형 객체 bw를 선언한다.
	static int index = 1;
	// 메모리에 상주하게 int형 변수 index를 선언하고 1로 초기화한다.
	public static void main(String[] args) throws IOException {
	// 접근제어자 public으로 메모리에 상주하게 리턴 값이 없이 main 함수를 선언한다.
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		// BufferedReader 객체 bf를 선언한다.
		StringTokenizer st = new StringTokenizer(bf.readLine());
		// StringTokenizer 객체 st를 선언한다.
		a = Integer.parseInt(st.nextToken());
		// 공백을 기준으로 값을 입력받아 변수 a에 저장한다.
		b = Integer.parseInt(st.nextToken());
		// 공백을 기준으로 값을 입력받아 변수 b에 저장한다.
		arr = new int[b];
		// 배열 arr의 길이를 b로 한다.
		check = new boolean[a + 1];
		// 배열 visit의 길이를 a+1로 한다.
		bta(0);
		// 함수 bta를 매개변수 0으로 해서 호출한다.
		bw.flush();
		// 객체 bw에 저장된 값을 출력한다.
		bw.close();
		// 객체 bw의 사용을 종료한다.
	}
	
	public static void bta(int index) throws IOException {
	// 접근제어자 public으로 메모리에 상주하게 함수 bta를 선언한다.
		if (index == b) {
		// if문을 선언한다.
		
			for (int i = 0; i < b; i++) {
			// for문을 선언한다 i가 0~<a까지 반복한다.
				bw.write(arr[i] + " ");
				// 객체 bw에 arr[i]과 공란 내용을 저장한다.
				}
				
				bw.write("\n");
				// 객체 bw에 개행을 저장한다.
				return;
				// 메소드를 종료한다.
		}

				for (int i = 1; i <= a; i++) {
				// for문을 선언한다. i가 1~a일때 괄호안의 문장이 실행된다.
				
					if(!check[i]) {
					// if문을 선언한다. check[i]가 false일때 괄호안의 문장이 실행된다.
						arr[index] = i;
						// arr[index]에 i값을 저장한다.
						check[i] = true;
						// check[i]에 값 true를 저장한다.
						bta(index + 1);
						// 함수 bta를 매개변수 (index+1)로 호출한다.

						for (int j = i + 1; j <= a; j++)
						// for문 선언 j가 (i+1)~a일때 괄호안의 코드 반복
						{
						check[j] = false;
						// check[j]에 false 값 저장
 						}
 						
					}
				}
	}
}

 

[4] 결과