Algorithm
[알고리즘] 완전 탐색 - 중복 조합 (백준 15652번. N과 M(4) - JAVA)
오초의 기록
2022. 4. 9. 01:12
중복 조합
서로 다른 n개에서 순서 없이, 중복이 가능하게 r개를 뽑는 경우의 수
(1) 중복을 허용해서 (a) 고르기
ex) 조합은 순서가 없으므로 [1,2]와 [2,1]은 같은 것으로 취급한다.
백준 15652번. N과 M(4)
조건
- 같은 수를 여러 번 골라도 된다.
- 고른 수열은 비내림차순이어야 한다.
- 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
풀이 방법
- 재귀 사용(백트래킹)
- Scanner + StringBuffer
- 현재 선택한 원소를 포함하여 그 뒤의 것들을 선택 가능하므로 start 변수에 i를 담아 넘겨준다.
import java.util.Scanner;
public class Main {
static int N,M;
static int[] out;
static StringBuffer sb = new StringBuffer();
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
N = scanner.nextInt();
M = scanner.nextInt();
out = new int[M];
combination(0,1, out);
System.out.println(sb);
}
private static void combination(int depth, int start, int[] out) {
if(depth == M){
for(int num : out) sb.append(num).append(" ");
sb.append("\n");
return;
}
for(int i = start; i<=N; i++){
out[depth] = i;
combination(depth+1, i, out);
}
}
}