BOJ_S3_15657

📁 [S3_15657] N과M(8)

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;

	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];

		// 배열 값 넣기
		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;
		}
		else {
			for(int i=start;i<N;i++) {
			res[idx] = arr[i];
			comb(idx+1, i);	
			}
		}
	}
}

🤔 나의 생각

이 문제는 순서가 상관없기 때문에 조합문제이다.
이 문제의 키 포인트는 자기 자신을 포함하기 떄문에 원래 재귀를 돌릴때 (idx+1, i+1)를 주는데 i+1를 안주고 i를 준다.
그래서 본인보다 하나 더 큰 값부터 확인하는 것이 아니라 본인 값부터 확인을 한다. 조합에 대한 자세한 설명은 여기에 있다.