[백준] 15657번 : N과 M (8)

문제

 

 

접근 방식

1231 1231 1231 1231
1231 1231 1231 1232
1231 1231 1231 1233
1231 1231 1231 1234
1231 1231 1232 1232
1231 1231 1232 1233
1231 1231 1232 1234
1231 1231 1233 1233
1231 1231 1233 1234
1231 1231 1234 1234
1231 1232 1232 1232
1231 1232 1232 1233
1231 1232 1232 1234
1231 1232 1233 1233
1231 1232 1233 1234
1231 1232 1234 1234
1231 1233 1233 1233
1231 1233 1233 1234
1231 1233 1234 1234
1231 1234 1234 1234
1232 1232 1232 1232
1232 1232 1232 1233
1232 1232 1232 1234
1232 1232 1233 1233
1232 1232 1233 1234
1232 1232 1234 1234
1232 1233 1233 1233
1232 1233 1233 1234
1232 1233 1234 1234
1232 1234 1234 1234
1233 1233 1233 1233
1233 1233 1233 1234
1233 1233 1234 1234
1233 1234 1234 1234
1234 1234 1234 1234

 

위와 같이 주어진 배열을 정렬하여 오름차순으로 수열을 출력해 주면 되는데

다음에 오는 숫자는 처음이 아니라 항상 이전 숫자와 같은 인덱스에서부터 시작한다

예를 들어 이전에 1231을 뽑았으면 다음에 뽑을 수 있는 수는 1231, 1232, 1233, 1234고

이전에 뽑은 수가 1233이라면 다음에 뽑을 수 있는 수는 1233, 1234 뿐이다.

 

그래서 재귀를 호출할 때마다 현재 자신이 선택한 인덱스를 넘겨주면 된다.

 

풀이

public class Main {

	private static StringBuilder sb = new StringBuilder();
	private static int n;
	private static int m;
	private static int[] arr;
	private static int[] sequence;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		arr = new int[n];
		sequence = new int[m];

		st = new StringTokenizer(br.readLine(), " ");

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr);

		createSequence(0, 0);

		System.out.println(sb);
	}

	private static void createSequence(int size, int start) {
		if (size == m) {
			for (int i = 0; i < m; i++) {
				sb.append(sequence[i]).append(" ");
			}
			sb.append("\n");

			return;
		}

		for (int i = start; i < n; i++) {
			sequence[size] = arr[i];
			createSequence(size + 1, i);
		}
	}
}