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);
        }
    }
}