[백준] 자바 15657 N과 M(8)

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

테스트 케이스

 

입력 1

3 1
3 2 1

출력 1

1

2

3

 

입력 2

5 3
7 8 3 1 5

출력 2

1 1 1 
1 1 3 
1 1 5 
1 1 7 
1 1 8 
1 3 3 
1 3 5 
1 3 7 
1 3 8 
1 5 5 
1 5 7 
1 5 8 
1 7 7 
1 7 8 
1 8 8 
3 3 3 
3 3 5 
3 3 7 
3 3 8 
3 5 5 
3 5 7 
3 5 8 
3 7 7 
3 7 8 
3 8 8 
5 5 5 
5 5 7 
5 5 8 
5 7 7 
5 7 8 
5 8 8 
7 7 7 
7 7 8 
7 8 8 
8 8 8 

 

입력 3

3 2
9 10 5

출력 3

5 5 
5 9 
5 10 
9 9 
9 10 
10 10 

---

접근

정직한 조합 문제 입니다.

제가 올린 예제 3에서 

5 5

5 9

5 10

그리고

9 5 가 안나오는 이유는 for 시작 인덱스를 start로 줬기 때문입니다.

---

코드

import java.io.*;
import java.util.*;
public class Main {
	static int N,M,arr[],result[];
	public static void comb(int start, int cnt) {
		if(M == cnt) {
			for(int i : result) {
				System.out.print(i+" ");
			}
			System.out.println();
			return;
		}

		for(int i=start; i<N; i++) {
			result[cnt] = arr[i];
			comb(i,cnt+1);
		}
	}
	public static void main(String[] args) throws Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    N = Integer.parseInt(st.nextToken());
	    M = Integer.parseInt(st.nextToken());
	    arr = new int[N];
	    result = new int[M];
	    st = new StringTokenizer(br.readLine());
	    for(int i=0; i<N; i++) {
	    	arr[i] = Integer.parseInt(st.nextToken());
	    }
	    Arrays.sort(arr);
	    comb(0,0);
	    bw.flush();
	    bw.close();
	    br.close();
	    }
	}

---

주의

x