[백준]15651번 N과 M(3)(JAVA)

0. 문제 링크

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

15651번: N과 M (3)

 

1. 문제 설명

1) 1부터 N까지 자연수 중에서 중복 가능한 M개를 고른 수열 구하기 -> 중복 순열

 

2. 입출력

// input
4 2

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

 

3. 코드

import java.io.*;
import java.util.StringTokenizer;

public class b15651 {
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		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);
		
		bw.flush(); // flush로 시간 초과 해결
		bw.close();
	}
	
	// arr : 원본 배열, sel : 선택 배열, idx : 원본 배열 인덱스, k : 선택 배열 인덱스
	private static void recursive(int[] arr, int[] sel, int idx, int k) throws IOException {
		// basis part
		if(k == sel.length) { // M개 골랐으면 출력
			for(int s = 0; s < sel.length; s++) {
				sb.append(sel[s] + " ");
			}
			sb.append("\n");
			bw.write(sb.toString());
			sb.setLength(0);
			return;
		}
		
		// inductive part
		for(int i = 0; i < arr.length; i++) {
			sel[k] = arr[i]; // 하나 선택하기
			recursive(arr, sel, idx+1, k+1);
		}
	}
}

 

실행 결과

 

4. 회고

1) 중복 순열 재귀로 구현

2) N이 커질수록 연산 시간이 길어지므로 BufferedWriter를 이용하여 시간 초과 해결

 

5. Github

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