순열과 조합

📝 기본 개념

순열과 조합은 공식이 아닙니다.

순열과 조합 - 순열2. 팩토리얼(factorial), 계승

조합은 뽑기, 순서는 상관없다.

파스칼의 삼각형 - 자바실험실

 

📌 예시 문제

1.중복순열 구하기

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

 

입력 설명

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

 

출력 설명

첫 번째 줄에 결과를 출력합니다.

출력순서는 사전순으로 오름차순으로 정렬합니다.

 

입력 예제

3 2

 

출력 예제

1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

 

코드 구현

import java.util.*;

public class Main {
    static int maxNum;
    static int pickNum;
    static int[] pm;

    public static void main(String[] args) {
        Main q = new Main();

        Scanner scanner = new Scanner(System.in);
        maxNum = scanner.nextInt();
        pickNum = scanner.nextInt();
        pm = new int[pickNum];
        q.dfs(0);
    }

    public void dfs(int level) {
        if (level == pickNum) {
            for (int x : pm) {
                System.out.print(x + " ");
            }
            System.out.println();
        } else {
            for (int i = 1; i <= maxNum; i++) {
                pm[level] = i;
                dfs(level + 1);
            }
        }
    }
}

 

2.동전교환

다음과 같이 여러 단위의 동전들이 주어져 있을 때, 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한히 쓸 수 있다.

 

입력 설명

첫 번째 줄에는 동전의 종류 개수 N(1<=N<12)이 주어진다.

두 번째 줄에는 N개의 동전의 종류가 주어지고, 그 다음줄에 거슬러줄 금액 M(1<=M<=500)이 주어진다.

각 동전의 종류는 100원을 넘지 않는다.

 

출력 설명

첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.

 

입력 예제

3
1 2 5
15

 

출력 예제

3

 

ㄴ 5 5 5 동전 3개로 거슬러 줄 수 있다.

 

코드 구현

import java.util.*;

public class Main {
    static int numOfCoins;
    static Integer[] coins;
    static int targetSum;
    static int minLevel = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Main q = new Main();

        Scanner scanner = new Scanner(System.in);
        numOfCoins = scanner.nextInt();
        coins = new Integer[numOfCoins];
        for (int i = 0; i < numOfCoins; i++) {
            coins[i] = scanner.nextInt();
        }
        targetSum = scanner.nextInt();

        // 큰 숫자부터 확인하는 것이 이득
        Arrays.sort(coins, Collections.reverseOrder());

        q.dfs(0, 0);
        System.out.print(minLevel);
    }

    public void dfs(int level, int sum) {
        if (sum > targetSum) return;
        if (level >= minLevel) return;
        if (sum == targetSum) {
            minLevel = Math.min(minLevel, level);
        } else {
            for (int i = 0; i < numOfCoins; i++) {
                dfs(level + 1, sum + coins[i]);
            }
        }
    }
}

 

3.순열 구하기

10이하의 N개의 자연수가 주어지면, 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다.

 

입력 설명

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

두 번째 줄에 N개의 자연수가 오름차순으로 주어집니다.

 

출력 설명

첫 번째 줄에 결과를 출력합니다.

출력순서는 사전순으로 오름차순으로 출력합니다.

 

입력 예제

3 2
3 6 9

 

출력 예제

3 6
3 9
6 3
6 9
9 3
9 6

 

코드 구현

import java.util.*;

public class Main {
    static int numOfNumbers;
    static int pickNum;
    static int[] numbers;
    static int[] check;
    static int[] pm;

    public static void main(String[] args) {
        Main q = new Main();

        Scanner scanner = new Scanner(System.in);
        numOfNumbers = scanner.nextInt();
        pickNum = scanner.nextInt();
        numbers = new int[numOfNumbers];
        check = new int[numOfNumbers];
        pm = new int[pickNum];
        for (int i = 0; i < numOfNumbers; i++) {
            numbers[i] = scanner.nextInt();
        }

        q.dfs(0);
    }

    private void dfs(int level) {
        if (level == pickNum) {
            for (int i = 0; i < pickNum; i++) {
                System.out.print(pm[i] + " ");
            }
            System.out.println();
        } else {
            for (int i = 0; i < numOfNumbers; i++) {
                if (check[i] == 0) {
                    check[i] = 1;
                    pm[level] = numbers[i];
                    dfs(level + 1);
                    check[i] = 0;
                }
            }
        }
    }
}

 

4.조합수

조합은 아래와 같은 공식으로 계산하나, 이 공식을 사용하지 않고

 

다음 공식을 사용하여, 재귀를 이용해 조합수를 구하는 프로그램을 작성하세요.

 

입력 설명

첫째 줄에 자연수 n(3<=n<=33)과 r(0<=r<=n)이 입력됩니다.

 

출력 설명

첫째 줄에 조합수를 출력합니다.

 

입력 예제

33 19

 

출력 예제

818809200

 

코드 구현

import java.util.*;

public class Main {
    static int[][] memo;

    public static void main(String[] args) {
        Main q = new Main();

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int r = scanner.nextInt();
        memo = new int[35][35];
        q.combi(n, r);
        System.out.print(memo[n][r]);
    }

    private int combi(int n, int r) {
        if (memo[n][r] > 0) return memo[n][r];
        if (n == r || r == 0) {
            return memo[n][r] = 1;
        } else {
            return memo[n][r] = combi(n - 1, r - 1) + combi(n - 1, r);
        }
    }
}

 

5.수열 추측하기

가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두 개를 더한 값이 저장되게 된다.

예를 들어, N이 4이고 가장 윗 줄에 3 1 2 4가 있다고 할 때 다음과 같은 삼각형이 그려진다.

3 1 2 4

 4 3 6

  7  9

   16

 

N과 가장 밑에 있는 숫자가 주여져 있을 때, 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오.

단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.

 

입력 설명

첫째 줄에 두 개의 정수 N(1<=N<=10)과 F가 주어진다. N은 가장 윗줄에 있는 숫자의 개수를 의미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다.

 

출력 설명

첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다.

답이 존재하지 않는 경우는 입력으로 주어지지 않는다.

 

입력 예제

4 16

 

출력 예제

3 1 2 4

 

코드 구현

import java.util.*;

public class Main {
    static int numOfNumbers;
    static int targetNum;
    static int[][] memo;
    static int[] numbers;
    static int[] check;
    static int[] pm;
    static boolean flag = false;

    public static void main(String[] args) {
        Main q = new Main();

        Scanner scanner = new Scanner(System.in);
        numOfNumbers = scanner.nextInt();
        targetNum = scanner.nextInt();

        numbers = new int[targetNum];
        check = new int[targetNum];
        for (int i = 0; i < numOfNumbers; i++) {
            numbers[i] = i + 1; // 1, 2, 3, ...    
        }

        pm = new int[numOfNumbers];

        // 이항계수 구해놓기
        memo = new int[numOfNumbers][numOfNumbers];
        for (int r = 0; r < numOfNumbers; r++) {
            q.combi(numOfNumbers - 1, r);
        }

        // 순열 구하기
        q.dfs(0, 0);
    }

    private void dfs(int level, int sum) {
        if (flag) return;
        if (level == numOfNumbers) {
            if (sum == targetNum) {
                for (int x : pm) {
                    System.out.print(x + " ");
                }
                flag = true;
            }
        } else {
            for (int i = 0; i < numOfNumbers; i++) {
                if (check[i] == 0) {
                    check[i] = 1;
                    pm[level] = numbers[i];
                    dfs(level + 1, sum + pm[level] * memo[numOfNumbers - 1][level]);
                    check[i] = 0;
                }
            }
        }
    }

    private int combi(int n, int r) {
        if (memo[n][r] > 0) return memo[n][r];
        if (n == r || r == 0) {
            return memo[n][r] = 1;
        } else {
            return memo[n][r] = combi(n - 1, r - 1) + combi(n - 1, r);
        }
    }
}

 

6.조합 구하기

1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요.

 

입력 설명

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

 

출력 설명

첫 번째 줄에 결과를 출력합니다.

출력순서는 사전순으로 오름차순으로 출력합니다.

 

입력 예제

4 2

 

출력 예제

1 2
1 3
1 4
2 3
2 4
3 4

 

구현 코드

import java.util.*;

public class Main {
    static int n;
    static int r;
    static int[] numbers;
    static int[] combi;

    public static void main(String[] args) {
        Main q = new Main();

        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        r = scanner.nextInt();
        numbers = new int[n];
        combi = new int[r];
        for (int i = 0; i < n; i++) {
            numbers[i] = i + 1; // 1, 2, 3, ...
        }
        q.dfs(0, 0);
    }

    private void dfs(int level, int start) {
        if (level == r) {
            for (int x : combi) {
                System.out.print(x + " ");
            }
            System.out.println();
        } else {
            for (int i = start; i < n; i++) {
                combi[level] = numbers[i];
                dfs(level + 1, i + 1);
            }
        }
    }
}