BOJ_S3_15655
๐ [S3_15655] N๊ณผM(6)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static StringTokenizer st;
static StringBuilder sb;
static int N,M;
static int[] arr;
static int[] res;
static boolean[] v;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N];
// ์กฐํฉ ๊ตฌํ ๋ ์ฌ์ฉํ ๋ฐฐ์ด
res = new int[M];
v = new boolean[N+1];
// ๋ฐฐ์ด ๊ฐ ๋ฃ๊ธฐ
st = new StringTokenizer(br.readLine()," ");
for(int i=0; i<N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
// ์ ๋ ฌํ๊ธฐ
Arrays.sort(arr);
comb(0,0);
System.out.println(sb);
}
// ์์๊ฐ ์๊ด์๊ธฐ ๋๋ฌธ์ ์กฐํฉ
static void comb(int idx, int start) {
// ๊ธฐ์ ์กฐ๊ฑด
if(idx == M) {
for(int i=0; i<M; i++) {
sb.append(res[i]).append(" ");
}
sb.append("\n");
return;
}
for(int i=start; i<N; i++) {
if(v[i]) {
continue;
}
else {
v[i] = true;
res[idx] = arr[i];
comb(idx+1, i+1);
v[i] = false;
}
}
}
}
๐ค ๋์ ์๊ฐ
์ด ๋ฌธ์ ๋ ์์๊ฐ ์๊ด์๊ธฐ ๋๋ฌธ์ ์กฐํฉ๋ฌธ์ ์ด๋ค.
์
๋ ฅ ๋ฐ์ ๊ฐ๋ค์ ์ ๋ ฌ์ํค๊ณ ์กฐํฉ ์๊ณ ๋ฆฌ์ฆ ๊ณผ์ ์ ๊ฑฐ์ณ์ฃผ๋ฉด ๋๋ค.
์์๊ฐ ์๊ด์๋ค๋ ์๋ฏธ๋ (1,2) ๊ฐ (2,1) ์ด๋ ๊ฐ์ ๊ฐ์ ์๋ฏธํ๋ค๋ ๋ป์ด๋ค. ๊ทธ๋์ ํ๋์ ๊ฐ๋ง ์ถ๋ ฅํด์ฃผ๋ฉด ๋๋ค.
์กฐํฉ์ ๋ํ ์์ธํ ์ค๋ช
์ ์ฌ๊ธฐ์ ์๋ค.