문제

BOJ 15664: N과 M (10) https://www.acmicpc.net/problem/15664

조건 확인

• N개의 자연수 중에서 M개를 고른 수열을 출력한다.
• 고른 수열은 비내림차순(자기 자신을 포함하는 오름차순)이어야 한다.
• 중복할 수 없다.
• 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이

• 입력받은 배열을 오름차순으로 정렬한다.
• dfs에 start 인자를 받도록 하여 배열에 넣는 수가 오름차순이 되도록 한다.
• before 변수를 사용해 배열 내 이전 값과 현재 값이 중복인지 아닌지 파악한다.
• 출력할 배열에 중복된 수가 들어오지 않도록 하기 위해 boolean 변수 isVisited를 추가한다.

코드

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

public class Main {
	
	static int N, M;
	static int[] arr, printArr;
	static boolean[] isVisited;
	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];
		isVisited = new boolean[N];
		for(int i=0; i<N; i++) {
			arr[i] = sc.nextInt();
		}
		
		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]).append(" ");
			}
			sb.append("\n");
			return;
		}
		
			int before = -1;
		for(int i=start; i<N; i++) {
			int now = arr[i];
			if(before == now || isVisited[i]) { // 중복된 수 이거나 이미 방문한 수라면 통과함
				continue;
			} else { // 아직 방문도 하지 않았고 중복된 수도 아니라면
				before = now;
				isVisited[i] = true;
				printArr[depth] = arr[i];
				dfs(i + 1, depth + 1);
				isVisited[i] = false;
			}
		}
	}
}

정리

• dfs를 재귀 호출할 때 dfs(start + 1, depth + 1)을 하여 원하는 출력값이 나오지 않았다.