[백준_15656번] N과 M (7)

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

15656번: N과 M (7)

[문제]

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.입력

 

[입력 조건]

• 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)
• 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

 

[코드]

import java.util.*;

public class BaekJoon_15656 {
	static int n,k;
	static int[] arr,print;
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		k=sc.nextInt();
		arr=new int[n];
		print=new int[k];
		
		for(int i=0;i<n;i++)
			arr[i]=sc.nextInt();
		
		Arrays.sort(arr);
		
		dfs(0);
		System.out.println(sb);
	}
	
	static void dfs(int depth) {
		// 선택된 k개의 수 sb에 저장 저장
		if(depth==k) {
			for(int i=0;i<print.length;i++)
				sb.append(print[i]+" ");
			sb.append('\n');
			return;
		}
		
		// 백트래킹
		for(int i=0;i<n;i++) {
			print[depth]=arr[i];
			dfs(depth+1);
		}
	}

}

 

[고찰]

 이번 문제는 수의 중복을 허용하기 때문에 방문 여부를 체크하는 visited 배열을 따로 사용하지 않아도 된다. 그리고 선택된 숫자를 담은 배열을 바로 출력하는 방식으로 구성한 코드를 제출했지만 시간초과를 받았다. 시간초과를 받지 않기 위해서는 StringBuilder에 수열을 모두 저장한 후 한번에 출력하는 방식을 사용해야 한다. 생각지 못한 시간초과 오류 외어는 어렵지 않은 문제였다.