[백준/Java] 15666: N과 M (12)

문제: https://www.acmicpc.net/problem/15666

 

 

조건

• TimeLimit = 2s
• N개중 M개를 고른 수열 (1<=N<=M<=8)
• 수열 내에서 중복이 가능하지만, 수열은 비내림 차순이어야 한다
• 가능한 수열들을 사전순으로 출력하라

 

풀이

• 완전탐색
  
  • N과 M이 모두 8이라면 -> 8*8*8*...*8 = 8^8 = 대략 1600만. 따라서 완전탐색 가능
  • 중복 가능하므로 visited 필요없음
  • 대신 이전에 고른 수보다 커야하므로, 이전에 고른 수의 index를 들고다니자
  • 이때 기존 배열을 정렬해줘야지 비내림차순이 가능하다
  • 또한 한번 골랐던 '수'(index 아님)를 또 고르지 않기 위해, 한번 골랐던 수를 기억해두자

 

코드

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


public class Main {

	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int n;
	static int m;
	static int[] arr;
	static int[] select;
	
	public static void main(String[] args) throws IOException {

		// input
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		arr = new int[n];
		st = new StringTokenizer(br.readLine());
		for (int i=0; i<n; i++) arr[i] = Integer.parseInt(st.nextToken());
		Arrays.sort(arr);
		
		// dfs
		select = new int[m];
		dfs(0, 0);
		
		// result
		System.out.print(sb);
	}
	
	
	
	static void dfs(int size, int cur) {
		
		if (size == m) {
			for (int i=0; i<m; i++) sb.append(select[i]).append(" ");
			sb.append("\n");
			return;
		}
		
		int pre = -1;
		for (int i=cur; i<n; i++) {
			if (arr[i] == pre) continue;
			pre = arr[i];
			select[size] = arr[i];
			dfs(size+1, i);
		}
		
	}
	
	
}