중복순열 구하기

13 May 2023 in Algorithm on Java, Coding, Test

문제

문제

1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열 하는 방법을 모두 출력합니다.

입력

첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.

출력

첫 번째 줄에 결과를 출력합니다. 출력순서는 사전순으로 오름차순으로 출력합니다.

입력예제 1

32

출력예제 1

11
12
13

21
22
23
31
32
33

해결방법

• 중복 순열 구할 때, 해당 레벨에서 나머지 원소 부분집합을 다 만들어야 함.
• 따라서, 그림과 코드 처럼 한 레벨에서 나머지 부분집합을 다 찾기 위해 반복문을 통해 내부에서 DFS 재귀호출을 함.

코드

import java.util.Scanner;

public class Main {

    static int[] pm;
    static int n, m;

    public void DFS(int L) {
        if (L == m) {
            for (int x : pm) System.out.print(x + " ");
            System.out.println();
        } else {
            for (int i = 1; i <= n; i++) {
                pm[L] = i; // 그림 참고
                DFS(L + 1);
            }
        }
    }

    public static void main(String[] args) {
        Main cls = new Main();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();
        pm = new int[m];
        cls.DFS(0);
    }
}