문제

BOJ 15656: N과 M (7) https://www.acmicpc.net/problem/15656

조건 확인

• N개의 자연수 중에서 M개를 고른 수열을 출력한다.
• 중복할 수 있다.
• 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이

• 입력받은 배열인 arr을 오름차순으로 정렬한 뒤 dfs 함수를 실행한다.
• dfs함수에 depth 인자만 전달해 줘도 된다.

코드

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

public class Main {
	
	static int N, M;
	static int[] arr, printArr;
	static StringBuilder sb = new StringBuilder(); // 시간초과 해결용
	
	public static void main(String[] args) throws IOException{
			Scanner sc = new Scanner(System.in);
			
			N = sc.nextInt();
			M = sc.nextInt();
			
			arr = new int[N];
			printArr = new int[M];
			
			for(int i=0; i<N; i++) {
				arr[i] = sc.nextInt();
			}
			sc.close();
			
			Arrays.sort(arr); // 입력받은 배열을 오름차순으로 정렬한다.
			
			dfs(0, 0);
			
			System.out.println(sb);
	}
	
	static void dfs(int start, int depth) {
		if(depth == M) {
			for(int i=0; i<M; i++) {
				sb.append(printArr[i] + " ");
			}
			sb.append("\n");
			return;
		}
		
		for(int i=0; i<N; i++) {
			printArr[depth] = arr[i];
			dfs(i + 1, depth + 1); 
		}
	}
}

정리

• 오름차순으로 정렬하여 DFS를 사용하기만 하면 된다.