[백준]15650번 N과 M(2)(JAVA)

0. 문제 링크

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

1. 문제 설명

1) 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 구하기 -> 조합

 

2. 입출력

// input
4 2

// output
1 2
1 3
1 4
2 3
2 4
3 4

 

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class b15650 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 1. 입력
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		// 2. N개 중에 중복 없이 M개 고르기
		int[] arr = new int[N]; // 원본 배열 
		int[] sel = new int[M]; // 선택 배열
		
		for(int n = 0; n < N; n++) { // 원본 배열 생성
			arr[n] = n+1;
		}
		
		recursive(arr, sel, 0, 0);
	}
	
	// arr : 원본 배열, sel : 선택 배열, idx : 원본 배열 인덱스, k : 선택 배열 인덱스
	private static void recursive(int[] arr, int[] sel, int idx, int k) {
		// basis part
		if(k == sel.length) { // M개 골랐으면 출력
			for(int s = 0; s < sel.length; s++) {
				System.out.print(sel[s] + " ");
			}
			System.out.println();
			return;
		}
		
		// inductive part
		for(int i = idx; i < arr.length; i++) { // idx에서 시작해서 arr.length만큼
			sel[k] = arr[i]; // 하나 선택하기
			recursive(arr, sel, i+1, k+1);
		}
	}
}

 

실행 결과

 

4. 회고

1) 조합 재귀로 구현

 

5. Github

https://github.com/iihye/Algorithm/blob/main/Baekjoon/b15650.java