문제 - 건너 뛰며 해보기

건너 뛰며 해보기는 모든 경우의 수를 다 해볼 필요가 없다고 느껴질 때 몇개를 건너 뛰며 계산하는 방법이다.

1. 문제 : 카잉 달력

M과 N보다 작거나 같은 두 자연수 x,y를 이용해서 년도를 <x:y>로 표현한다. 이때 M,N,x,y 가 주어졌을 때 <x:y>가 몇번째 해인지 구하는 문제이다.
조건은 첫번째 해는 <1:1>, 두번째 해는 <2:2>이와같이 진행이되며 <x:y>의 다음해는 <x':y'>이다. x<M이면 x'=x+1 이고 아니면 x'=1이다. 마찬가지로 y<N이면 y'=y+1 이고 아니면 y'=1이다.

M,N의 범위가 최대 40,000이기 대문에 전체 경우의수는 16억이 나온다. 이를 다 하기에는 오랜시간이 걸리기 때문에 나머지연산을 이용하여 건너뛰며 문제를 해결하면 된다.

예를들어 M = 5, N = 7이 주어지고 <2,5>가 주어졌다고 해보자. 그리고 M과 N을 처음부터 하나씩 써나가면 아래와같이 M은 1~5 N은 1~7이 반복되는 것을 볼 수 있다.

1 : <1,1> 8 : <3,1>
2 : <2,2> 9 : <4,2>
3 : <3,3> 10: <5,3>
4 : <4,4> 11: <1,4>
5 : <5,5> 12: <2,5>
6 : <1,6> 13: <3,6>
7 : <2,7> 14: <4,7>

x=2 이니까 2부터 시작해서 M을 더해가며 찾아주면 된다. 즉 2: <2,2> -> 7: <2,7> 이런식으로 말이다. 그러면 <2,5>가 나오는 부분이 문제의 해답인 것이다.

나머지 연산을 사용하려면 먼저 x-1, y-1를 해주고 그다음 M 또는 N으로 나머지연산을 해준 뒤 결과를 출력할 때는 +1를 해주면 된다.

<2,5> -(빼기 1)-> <1,4> -> <1%5, 4%5>
--> 11번째가 나온고 답은 12가 된다.

public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.valueOf(br.readLine());
		while (t-- > 0) {
			String[] line = br.readLine().split(" ");
			int m = Integer.valueOf(line[0]);
			int n = Integer.valueOf(line[1]);
			int x = Integer.valueOf(line[2]) - 1;
			int y = Integer.valueOf(line[3]) - 1;
			boolean ok = false;
			for (int k = x; k < (m * n); k += m) {
				if (k % n == y) {
					System.out.println(k + 1);
					ok = true;
					break;
				}
			}
			if (!ok) {
				System.out.println(-1);
			}
		}
	}

2. 문제 : 수 이어 쓰기 1

1부터 N까지 수를 이어서 스면 새로운 하나의 수를 얻는데, 이때 이 수는 몇자리 수인지 구하는 문제이다.
이 문제에서 N이 최대 1억까지이기 때문에 1억번을 다 연산을 해야하는 문제가 발생한다. 따라서 여기서는 수의 자리수를 이용하여 문제를 해결해야한다. 1~9 까지는 1자리수, 10~99까지는 2자리수 이렇게 하게되면 1억까지 포함하면 9번 정도 연산을 하면 되서 앞서 말한 1억번보다는 훨씬 적은 연산으로 문제가 해결된다.

예를들어 N=120이면 1~9 까지 9개 10~99은 (99-10+1)개 100~120은 (120-100+1)개 나오고 이를 자리수에 맞춰 더하면 19 + 2(99-10+1) + 3* (120-100+1) = 252 가 나온다.

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long ans = 0;
		for (int start = 1, len = 1; start <= n; start *= 10, len++) {
			int end = start * 10 - 1;
			if (end > n) {
				end = n;
			}
			ans += (long) (end - start + 1) * len;
		}
		System.out.println(ans);
	}

문제 - N중 for문

N개 중에 일부를 선택해야 하는 경우에 많이 사용한다. 중복되는 부분이 많아서 잘 사용하지 않고 주로 재귀 호출이나 비트마스크를 사용하여 구현한다.

1. 문제 : 1,2,3 더하기

정수 N을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제이다. 앞서 DP로 푼 문제이긴 한데, 이 문제의 N의 범위가 10이하의 수이기 때문에 for문을 10번만 하면 문제를 해결할 수 있는 작은 문제이다.
즉, (1,2,3) + (1,2,3) +...+ (1,2,3) 각각의 1,2,3을 한번씩 해서 구하는 것이다.

public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while (t-- > 0) {
			int n = sc.nextInt();
			int ans = 0;
			for (int l1 = 1; l1 <= 3; l1++) {
				if (l1 == n) {
					ans += 1;
				}
				for (int l2 = 1; l2 <= 3; l2++) {
					if (l1 + l2 == n) {
						ans += 1;
					}
					for (int l3 = 1; l3 <= 3; l3++) {
						if (l1 + l2 + l3 == n) {
							ans += 1;
						}
						for (int l4 = 1; l4 <= 3; l4++) {
							if (l1 + l2 + l3 + l4 == n) {
								ans += 1;
							}
							for (int l5 = 1; l5 <= 3; l5++) {
								if (l1 + l2 + l3 + l4 + l5 == n) {
									ans += 1;
								}
								for (int l6 = 1; l6 <= 3; l6++) {
									if (l1 + l2 + l3 + l4 + l5 + l6 == n) {
										ans += 1;
									}
									for (int l7 = 1; l7 <= 3; l7++) {
										if (l1 + l2 + l3 + l4 + l5 + l6 + l7 == n) {
											ans += 1;
										}
										for (int l8 = 1; l8 <= 3; l8++) {
											if (l1 + l2 + l3 + l4 + l5 + l6 + l7 + l8 == n) {
												ans += 1;
											}
											for (int l9 = 1; l9 <= 3; l9++) {
												if (l1 + l2 + l3 + l4 + l5 + l6 + l7 + l8 + l9 == n) {
													ans += 1;
												}
												for (int l0 = 1; l0 <= 3; l0++) {
													if (l1 + l2 + l3 + l4 + l5 + l6 + l7 + l8 + l9 + l0 == n) {
														ans += 1;
													}
												}
											}
										}
									}
								}
							}
						}
					}
				}
			}
			System.out.println(ans);
		}
	}

문제 - N과 M 시리즈

브루트 포스에서 방법을 만드는 방법에는 크게 3가지가 존재한다. 1. 재귀 2. 순열 3. 비트마스크 이렇게 있는데, 재귀로 하는 방법이 제일 중요하다. 이유는 순열과 비트마스크로 풀 수 있는 문제는 재귀로도 풀 수 있기 때문이다.

재귀를 사용하는 브루트 포스는 크게 순서, 선택 두가지로 나눌 수 있다.

1. 문제 : N과 M (1)

1부터 N가지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제이다. 범위는 $1 \leq M \leq N \leq 8$이다.
이 문제는 순서를 구하는 문제라 볼 수 있는데, 예를 들어 N = 5, M = 3이라 했을 때 (1 2 3), (1 2 4), (1 2 5), (1 3 2) 이런식으로 올 수 있다. _ _ _ 이렇게 3자리가 있으면 첫 번째 자리에는 1~5까지 5가지가 올 수 있고 그 다음 두 번째 자리에는 앞에 온 수를 제외한 나머지 수들이 올 수 있다.
이것을 이용하기 위해 boolean 배열을 만들어 해당 인덱스(=사용한 수)를 기준으로 판별할 수 있다.
따라서 해당 index 자리에 올 수 있는 수는 1 ~ N 이며 배열[i] == false 인 것들이다.

아래 코드의 go함수를 보면 매개변수 index는 index 번째를 채우려고 함을 의미한다. 또한 제일 먼저 index 가 m인 경우일 때 (= 배열 마지막 인덱스를 넘어서는 경우) 정답이 들어간 배열을 출력한다.
그리고 for문 안에서 마지막에 c[i] = false를 한 이유는 if문에 걸려 출력을 하고 난 뒤에는 다시 이미 썻던 수는 쓰지 않음으로 표시해야 되기 때문이다.

public static boolean[] c = new boolean[10];
public static int[] a = new int[10];

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int m = sc.nextInt();
	go(0, n, m);
}

public static void go(int index, int n, int m) {
	if (index == m) {
		for (int i = 0; i < m; i++) {
			System.out.print(a[i]);
			if (i != m - 1)
				System.out.print(' ');
		}
		System.out.println();
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (c[i]) {
			continue;
		}
		c[i] = true;
		a[index] = i;
		go(index + 1, n, m);
		c[i] = false;
	}
}

2. 문제 : N과 M (2)

N과 M (1) 문제에서 결과 수열이 오름차순이다. 라는 조건만 추가된 문제이다.
오름차순이 적용되면 N = 5, M = 3 이라 했을 대 (1 2 3), (1 2 4), (1 2 5), (1 3 2), (1 3 4) 이렇게 (1 3 2) 는 올 수가 없다.
따라서 해당 index 자리에 어떤 수(=num)가 오면 그 다음 자리(=index+1)에는 num+1 ~ N까지의 수가 올 수 있다.

public static boolean[] c = new boolean[10];
	public static int[] a = new int[10];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		go(0, 1, n, m);

	}

	public static void go(int index, int start, int n, int m) {
		if (index == m) {
			for (int i = 0; i < m; i++) {
				System.out.print(a[i]);
				if (i != m - 1)
					System.out.print(' ');
			}
			System.out.println();
			return;
		}
		for (int i = start; i <= n; i++) {
			if (c[i]) {
				continue;
			}
			c[i] = true;
			a[index] = i;
			go(index + 1, i + 1, n, m);
			c[i] = false;
		}
	}

위의 코드에서 c[] 배열을 굳이 사용하지 않아도 되는데 그 이유는 다음 자리에 오는 수가 이전 자리의 수보다 항상 크기 때문에 중복이 되지 않는다. 따라서 c[] 배열을 사용하지 않아도 된다.

다른 방식으로도 이 문제를 풀 수 있는데, 이전 방식은 각각의 위치에 어떤 수를 추가해야 할지를 결정했는데 (=순서) 이번 방법은 M개의 수를 뽑아서 어떤 수가 들어갈지 결정하는 방법(=선택)이다.

예를 들어 1, 3, 5 3개를 선택 했다고 하면 (1 3 5), (1 5 3), (3 1 5), (3 5 1), (5 1 3), (5 3 1) 오름차순이 되는 것은 (1 3 5) 하나 밖에 없다. 즉, 어떤 수를 선택하면 오름차순이 되는 것은 하나 밖에 없는 것이다.

1, 2, 3, ... n-1, n 이렇게 있으면 각각의 자연수를 선택하는 경우와 섵낵하지 않는 경우가 존재한다. 이를 재귀함수를 이용하여 아래와 같은 코드처럼 나타낼 수 있다.

public static int[] a = new int[10];

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int m = sc.nextInt();
	go(1, 0, n, m);
}

public static void go(int index, int selected, int n, int m) {
	if (selected == m) {
		for (int i = 0; i < m; i++) {
			System.out.print(a[i]);
			if (i != m - 1) {
				System.out.print(" ");
			}
		}
		System.out.println();
		return;
	}
	if (index > n) {
		return;
	}
	a[selected] = index;
	go(index + 1, selected + 1, n, m);
	a[selected] = 0;
	go(index + 1, selected, n, m);
}

매개변수 index는 사용할 자연수를 의미하는데, index 라는 수를 선택할 지 말아야 할 지를 결정하는 것이다. 그 다음 selected는 현재까지 선택한 수의 개수이다. 따라서 selected 가 m이 되면 더이상 선택할 필요가 없기 때문에 출력을 하면 된다.

이 방법은 첫번째 방법보다 약간 빠른데 시간복잡도를 보면 첫번째 방법은 $O(N!)$이고 두번째 방법은 $O(2^N)$이다.

3. 문제 : N과 M (3)

N과 M (1) 문제에서 중복 선택이 가능하다는 것이 추가되었다. 따라서 코드상에 배열 c를 사용한 부분을 모두 지워주면 되는데, 지우기만 하면 자바에서는 시간초과가 발생하여 코드를 약간 변형해야한다.

public static int[] a = new int[10];

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int m = sc.nextInt();
	System.out.print(go(0, n, m));
}

public static StringBuilder go(int index, int n, int m) {
	if (index == m) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < m; i++) {
			sb.append(a[i]);
			if (i != m - 1) {
				sb.append(" ");
			}
		}
		sb.append("\n");
		return sb;
	}
	StringBuilder ans = new StringBuilder();
	for (int i = 1; i <= n; i++) {
		a[index] = i;
		ans.append(go(index + 1, n, m));
	}
	return ans;
}

4. 문제 : N과 M (4)

N과 M (2) 문제에서 중복이 허용됨이 추가된 문제이다. 예를 들면 1 1 2 2 3 이러한 형태를 말한다.

public static int[] a = new int[10];

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int m = sc.nextInt();
	System.out.print(go(0, 1, n, m));
}

public static StringBuilder go(int index, int start, int n, int m) {
	if (index == m) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < m; i++) {
			sb.append(a[i]);
			if (i != m - 1) {
				sb.append(" ");
			}
		}
		sb.append("\n");
		return sb;
	}
	StringBuilder ans = new StringBuilder();
	for (int i = start; i <= n; i++) {
		a[index] = i;
		ans.append(go(index + 1, i, n, m));
	}
	return ans;
}

5. 문제 : N과 M (5)

N과 M (1~4) -> N과 M(5~8) 문제가 비슷함

N개의 서로 다른 자연수 중에서 M개를 고른 수열을 모두 구하는 문제이다.
앞서 푼 문제에서 num 배열이 추가되었는데 이 num 배열은 입력받은 수를 저장하는 공간이다.

public static boolean[] c = new boolean[10];
public static int[] a = new int[10];
public static int[] num = new int[10];

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int m = sc.nextInt();
	for (int i = 0; i < n; i++) {
		num[i] = sc.nextInt();
	}
	Arrays.sort(num, 0, n);
	System.out.print(go(0, n, m));
}

public static StringBuilder go(int index, int n, int m) {
	if (index == m) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < m; i++) {
			sb.append(num[a[i]]);
			if (i != m - 1) {
				sb.append(" ");
			}
		}
		sb.append("\n");
		return sb;
	}
	StringBuilder ans = new StringBuilder();
	for (int i = 0; i < n; i++) {
		if (c[i]) {
			continue;
		}
		c[i] = true;
		a[index] = i;
		ans.append(go(index + 1, n, m));
		c[i] = false;
	}
	return ans;
}

6. 문제 : N과 M (6)

5번 문제의 오름차순 추가

public static boolean[] c = new boolean[10];
public static int[] a = new int[10];
public static int[] num = new int[10];

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int m = sc.nextInt();
	for (int i = 0; i < n; i++) {
		num[i] = sc.nextInt();
	}
	Arrays.sort(num, 0, n);
	System.out.print(go(0, 0, n, m));
}

public static StringBuilder go(int index, int start, int n, int m) {
	if (index == m) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < m; i++) {
			sb.append(num[a[i]]);
			if (i != m - 1) {
				sb.append(" ");
			}
		}
		sb.append("\n");
		return sb;
	}
	StringBuilder ans = new StringBuilder();
	for (int i = start; i < n; i++) {
		if (c[i]) {
			continue;
		}
		c[i] = true;
		a[index] = i;
		ans.append(go(index + 1, i + 1, n, m));
		c[i] = false;
	}
	return ans;
}

7. 문제 : N과 M (7)

문제 5번에서 중복 허용이 추가된 문제

public static int[] a = new int[10];
public static int[] num = new int[10];

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int m = sc.nextInt();
	for (int i = 0; i < n; i++) {
		num[i] = sc.nextInt();
	}
	Arrays.sort(num, 0, n);
	System.out.print(go(0, n, m));
}

public static StringBuilder go(int index, int n, int m) {
	if (index == m) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < m; i++) {
			sb.append(num[a[i]]);
			if (i != m - 1) {
				sb.append(" ");
			}
		}
		sb.append("\n");
		return sb;
	}
	StringBuilder ans = new StringBuilder();
	for (int i = 0; i < n; i++) {
		a[index] = i;
		ans.append(go(index + 1, n, m));
	}
	return ans;
}

8. 문제 : N과 M (8)

문제 6번에 중복 허용 추가된 문제

public static int[] a = new int[10];
public static int[] num = new int[10];

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int m = sc.nextInt();
	for (int i = 0; i < n; i++) {
		num[i] = sc.nextInt();
	}
	Arrays.sort(num, 0, n);
	System.out.print(go(0, 0, n, m));
}

public static StringBuilder go(int index, int start, int n, int m) {
	if (index == m) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < m; i++) {
			sb.append(num[a[i]]);
			if (i != m - 1) {
				sb.append(" ");
			}
		}
		sb.append("\n");
		return sb;
	}
	StringBuilder ans = new StringBuilder();
	for (int i = start; i < n; i++) {
		a[index] = i;
		ans.append(go(index + 1, i, n, m));
	}
	return ans;
}

9. 문제 : N과 M (9)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 문제이다.

문제 5번의 풀이에서 중복 제거를 포함해주면 된다.

public class Main {
	public static boolean[] c = new boolean[10];
	public static int[] a = new int[10];
	public static int[] num = new int[10];
	public static ArrayList<Result> d = new ArrayList<>();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		for (int i = 0; i < n; i++) {
			num[i] = sc.nextInt();
		}
		Arrays.sort(num, 0, n);
		go(0, n, m);
		Collections.sort(d);
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < d.size(); i++) {
			if (i == 0 || !d.get(i).equals(d.get(i - 1))) {
				for (int j = 0; j < m; j++) {
					sb.append(d.get(i).get(j));
					if (j != m - 1) {
						sb.append(" ");
					}
				}
				sb.append("\n");
			}
		}
		System.out.println(sb);
	}

	public static void go(int index, int n, int m) {
		if (index == m) {
			ArrayList<Integer> temp = new ArrayList<Integer>();
			for (int i = 0; i < m; i++) {
				temp.add(num[a[i]]);
			}
			d.add(new Result(temp));
			return;
		}
		for (int i = 0; i < n; i++) {
			if (c[i]) {
				continue;
			}
			c[i] = true;
			a[index] = i;
			go(index + 1, n, m);
			c[i] = false;
		}
	}

}

class Result implements Comparable<Result> {
	Integer[] a;

	public Result(ArrayList<Integer> a) {
		this.a = a.toArray(new Integer[a.size()]);
	}

	int get(int index) {
		return (int) this.a[index];
	}

	@Override
	public boolean equals(Object obj) {
		if (obj instanceof Result) {
			Result that = (Result) obj;
			int n = this.a.length;
			for (int i = 0; i < n; i++) {
				if (this.a[i] != that.a[i]) {
					return false;
				}
			}
			return true;
		} else {
			return false;
		}
	}

	public int compareTo(Result that) {
		int n = this.a.length;
		for (int i = 0; i < n; i++) {
			if (this.a[i] == that.a[i]) {
				continue;
			}
			if (this.a[i] < that.a[i]) {
				return -1;
			}
			if (this.a[i] > that.a[i]) {
				return 1;
			}
		}
		return 0;
	}

}

10. 문제 : N과 M (10)

문제 6번의 풀이에서 중복 제거를 포함해주면 된다.

9번 문제와 중복되는 코드는 제외함

public class Main {
	public static boolean[] c = new boolean[10];
	public static int[] a = new int[10];
	public static int[] num = new int[10];
	public static ArrayList<Result> d = new ArrayList<>();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		for (int i = 0; i < n; i++) {
			num[i] = sc.nextInt();
		}
		Arrays.sort(num, 0, n);
		go(0, 0, n, m);
		Collections.sort(d);
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < d.size(); i++) {
			if (i == 0 || !d.get(i).equals(d.get(i - 1))) {
				for (int j = 0; j < m; j++) {
					sb.append(d.get(i).get(j));
					if (j != m - 1) {
						sb.append(" ");
					}
				}
				sb.append("\n");
			}
		}
		System.out.println(sb);
	}

	public static void go(int index, int start, int n, int m) {
		if (index == m) {
			ArrayList<Integer> temp = new ArrayList<Integer>();
			for (int i = 0; i < m; i++) {
				temp.add(num[a[i]]);
			}
			d.add(new Result(temp));
			return;
		}
		for (int i = start; i < n; i++) {
			if (c[i]) {
				continue;
			}
			c[i] = true;
			a[index] = i;
			go(index + 1, i + 1, n, m);
			c[i] = false;
		}
	}

}

11. 문제 : N과 M (11)

N과 M (7)과 동일한 문제인데, 중복 선택을 할 수 있는 문제이다. 이 문제는 N개의 자연수에서 중복되는 수를 제거한 다음에 해결하면 된다.

문제 10번에서 중복을 체크하는 부분을 제거한다.

public class Main {
	public static int[] a = new int[10];
	public static int[] num = new int[10];
	public static ArrayList<Result> d = new ArrayList<>();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		for (int i = 0; i < n; i++) {
			num[i] = sc.nextInt();
		}
		Arrays.sort(num, 0, n);
		go(0, 0, n, m);
		Collections.sort(d);
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < d.size(); i++) {
			if (i == 0 || !d.get(i).equals(d.get(i - 1))) {
				for (int j = 0; j < m; j++) {
					sb.append(d.get(i).get(j));
					if (j != m - 1) {
						sb.append(" ");
					}
				}
				sb.append("\n");
			}
		}
		System.out.println(sb);
	}

	public static void go(int index, int start, int n, int m) {
		if (index == m) {
			ArrayList<Integer> temp = new ArrayList<Integer>();
			for (int i = 0; i < m; i++) {
				temp.add(num[a[i]]);
			}
			d.add(new Result(temp));
			return;
		}
		for (int i = start; i < n; i++) {
			a[index] = i;
			go(index + 1, 0, n, m);
		}
	}

}

12. 문제 : N과 M (12)

N과 M (8) 과 동일한 문제이며 앞에 11번 문제처럼 문제를 풀면 된다.

public class Main {
	public static int[] a = new int[10];
	public static int[] num = new int[10];
	public static ArrayList<Result> d = new ArrayList<>();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		for (int i = 0; i < n; i++) {
			num[i] = sc.nextInt();
		}
		Arrays.sort(num, 0, n);
		go(0, 0, n, m);
		Collections.sort(d);
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < d.size(); i++) {
			if (i == 0 || !d.get(i).equals(d.get(i - 1))) {
				for (int j = 0; j < m; j++) {
					sb.append(d.get(i).get(j));
					if (j != m - 1) {
						sb.append(" ");
					}
				}
				sb.append("\n");
			}
		}
		System.out.println(sb);
	}

	public static void go(int index, int start, int n, int m) {
		if (index == m) {
			ArrayList<Integer> temp = new ArrayList<Integer>();
			for (int i = 0; i < m; i++) {
				temp.add(num[a[i]]);
			}
			d.add(new Result(temp));
			return;
		}
		for (int i = start; i < n; i++) {
			a[index] = i;
			go(index + 1, i, n, m);
		}
	}

}

class Result implements Comparable<Result> {
	Integer[] a;

	public Result(ArrayList<Integer> a) {
		this.a = a.toArray(new Integer[a.size()]);
	}

	int get(int index) {
		return (int) this.a[index];
	}

	@Override
	public boolean equals(Object obj) {
		if (obj instanceof Result) {
			Result that = (Result) obj;
			int n = this.a.length;
			for (int i = 0; i < n; i++) {
				if (this.a[i].intValue() != that.a[i].intValue()) {
					return false;
				}
			}
			return true;
		} else {
			return false;
		}
	}

	public int compareTo(Result that) {
		int n = this.a.length;
		for (int i = 0; i < n; i++) {
			if (this.a[i] == that.a[i]) {
				continue;
			}
			if (this.a[i] < that.a[i]) {
				return -1;
			}
			if (this.a[i] > that.a[i]) {
				return 1;
			}
		}
		return 0;
	}

}

참고

백준 알고리즘 기초 강의를 듣고 공부하기 위해 정리한 것입니다.