728x90
N과 M (1)은 순열이었다면 N과 M (2)는 조합이다.
단계별로 풀어보기 백트래킹의 2단계 문제이다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
boolean[] visited = new boolean[n];
int[] result = new int[m];
combination(n, m, 0, visited, result);
}
static void combination(int n, int m, int num, boolean[] visited, int[] result) {
if (num == m) {
for (int i = 0; i < m; i++) {
System.out.print(result[i] + " ");
}
System.out.println();
}
else {
for (int i = 0; i < n; i++) {
if(!visited[i]) {
if(num != 0) {
if (result[num - 1] < i + 1) {
visited[i] = true;
result[num] = i + 1;
}
else continue;
}
else {
visited[i] = true;
result[num] = i + 1;
}
combination(n, m, num + 1, visited, result);
visited[i] = false;
}
}
}
}
}
응용할 것도 없이 그냥 조합이기 때문에 쉽게 풀 수 있었다.
728x90
'알고리즘 문제' 카테고리의 다른 글
[백준] 15652번 N과 M (4) (0) | 2020.01.06 |
---|---|
[백준] 15651 N과 M (3) (0) | 2020.01.06 |
[백준] 15649번 N과 M (1) (0) | 2020.01.06 |
[백준] 14502번 연구소 (0) | 2020.01.05 |
[백준] 12865 평범한 배낭 (0) | 2020.01.05 |