[백준] code.plus(브루트포스,JAVA)15654번, N과 M(5)

문제 링크

15654번: N과 M (5)

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

 

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

 

이 문제에서 오름차순으로 M개 수를 가진 수열이 나올 수 있는 경우의 수를 구하는 것이 핵심입니다.

 

배열

num : 수열에 들어갈 수 있는 숫자를 저장합니다.

 

check : num 배열에 있는 숫자가 현재 수열에 들어있는지 확인합니다.

 

result : 현재 수열의 값들을 저장합니다.

 

 

위에 3가지 배열과 재귀를 이용해서 문제를 구현하였습니다.

 

문제에 해결알고리즘은

1. num 배열을 오름차순 정렬합니다.

2. 재귀를 통해 수열에 들어갈 수 있는 경우의 수를 찾습니다.

3. 수열 들어간 숫자들은 result[]에 저장합니다.

4. 재귀 중 num[]에 숫자를 사용하였다면 check[]에 값을 변경합니다.

5. 재귀가 M번 반복되었을 때 현재 수열이 저장된 result[]를 결과에 저장합니다.

6. 재귀 종료시 모든 경우의 수를 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 이용하여 배열의 들어갈 수 있는 숫자들을 저장하였습니다.
• Arrays.sort()를 사용하여 배열을 오름차순 정렬하였습니다.
• 수열의 모든 경우의 수를 구하는 NandM함수를 만들었습니다.
• BufferedWriter에 수열의 모든 경우의 수를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• NandM는 재귀를 사용하여 모든 경우의 수를 구하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int[] num;		//수열에 들어가는 숫자 배열
	public static int[] result;		//수열 값 저장 배열
	public static boolean[] check;	//num에 숫자 수열에 들어갔는지 확인 배열
    public static StringBuilder sb = new StringBuilder();
    	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //-----입력값 저장 및 배열 초기화---------
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	int N = Integer.parseInt(st.nextToken());
    	int M = Integer.parseInt(st.nextToken());
    	num = new int[N];
    	check = new boolean[N];
    	result = new int[M];
    	st = new StringTokenizer(br.readLine()," ");
    	for(int i=0;i<N;i++) 
    		num[i] = Integer.parseInt(st.nextToken());
    	
    	Arrays.sort(num);		//num배열 오름차순 정렬
    	NandM(N,M,0);		// NandM 함수실행
    	bw.write(sb.toString() + "\n");		//결과 BufferedWriter에 저장
    	bw.flush();			//결과 출력
    	bw.close();
    	br.close();
    }
    //---------수열 경우의 수 구하는 재귀함수--------
    public static void NandM(int N, int M, int depth) {
    	if(M==depth) {		//수열 길이가 M일 때
    		for(int i=0;i<M;i++)
    			sb.append(result[i] + " ");
    		sb.append("\n");
    		return;
    	}
        //-----수열에 값 추가------
    	for(int i=0;i<N;i++) {
    		if(!check[i]) {
        		check[i] = true;
        		result[depth] = num[i];
        		NandM(N, M, depth+1);
        		check[i] = false;
    		}
    	}
    }
}