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

문제 링크

15657번: N과 M (8)

---

주의사항

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

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

---

문제 설명

---

접근 방법

브루트 포스란.

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

 

이 문제에서 비내림차순으로 M개 수를 가진 수열이 나올 수 있는 경우의 수를 구하는 것과 중복이 가능하다는 것이 핵심입니다.

 

배열

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

 

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

 

 

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

 

문제에 해결알고리즘은

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

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

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

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

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

 

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

• NandM는 재귀를 사용하여 모든 경우의 수를 구하였습니다.
• 중복 가능하기 때문에 for문의 반복 횟수가 수열의 들어갈 수 있는 모든 수를 포함시키도록 하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int[] num;		//숫자 저장 배열
	public static int[] result;		//수열 저장 배열
	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));
        //결과값 출력하는 BufferdWriter
        //-------입력값 처리 및 배열 초기화---------
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	int N = Integer.parseInt(st.nextToken());
    	int M = Integer.parseInt(st.nextToken());
    	num = new int[N+1];
    	result = new int[M+1];
    	st = new StringTokenizer(br.readLine()," ");
    	for(int i=1;i<=N;i++) {
    		num[i] = Integer.parseInt(st.nextToken());
    	}
    	Arrays.sort(num);		//오름차순 정렬
    	NandM(N, M, 1);		//함수 실행
    	bw.write(sb.toString() + "\n");		//결과 BufferedWriter 저장
    	bw.flush();			//결과 출력
    	bw.close();
    	br.close();
    	
    }
    //-------비내림차순 수열 경우의 수 구하는 함수-------
    public static void NandM(int N, int M, int depth) {
    	if(depth==M+1) {		//수열이 완성되었을 때
    		for(int i=1;i<=M;i++)
    			sb.append(result[i] + " ");
    		sb.append("\n");
    		return;
    	}
    	for(int i=1;i<=N;i++) {		//수열의 값 추가
    		if(result[depth-1]<=num[i]) {	//비내림차순인지 확인
    			result[depth] = num[i];
    			NandM(N, M, depth+1);
    		}
    	}
    }
}