[백준] no15650, 15652: N과 M (2, 3) - 기본 Combination 문제

문제

* 1부터 N까지의 숫자 중, M개를 고르는 모든 수열의 경우의 수를 구하기
* 단, 오름차순 정렬
* 단, N과 M은 1이상 8이하

문제 링크 : https://www.acmicpc.net/problem/15650

---

원리

전형적인 Combination (nCm) 문제 : 재귀를 이용한 풀이

참고 링크 : 멱집합 공식 기본 코드

import java.util.Arrays;

public class PowerSet_Combination {
    static int[] nums = { 1, 2, 3 };
    // 최대 원소의 개수
    static int max_cnt;
    // 각 부분 집합을 저장할 배열
    static int[] subset;

    public static void main(String[] args) {
        // 원소를 선택하는 개수 0 ~ 3개.
        for (int i = 0; i <= 3; i++) {
            max_cnt = i;
            subset = new int[i];
            // 대상 집합에서 원소를 0 ~ 3개를 선택하는 조합을 모두 구한다.
            Combination(0, 0);
        }
    }

    private static void Combination(int cnt, int k) {
        // 베이스코드
        if (cnt == max_cnt) {
            System.out.println(Arrays.toString(subset));
            return;
        }
        // 재귀 메서드 => 29번줄 코드를 통해 파라미터값을 변경하며 재귀함수가 진행된다
        for (int i = k; i < nums.length; i++) {
            subset[cnt] = nums[i];
            Combination(cnt + 1, i + 1);
        }
    }
}

---

풀이방법

Combination 계산을 위한 static method를 만들어 간단하게 풀이할 수 있다.

    private static void Combination (int cnt, int k) throws IOException {
        if(cnt == M) {
            for(int i = 0 ; i<M ; i++) bw.append(""+subset[i]+" ");
            bw.append("\n");
            return;
        }

        for(int i = k; i<N ; i++) {
            subset[cnt] = nums[i];
            Combination(cnt+1, i);  // 중복을 허용하는 경우
//            Combination(cnt + 1, i + 1); // 중복을 허용하지 않는 경우
        }
    }

---

나의 코드

1. no15650 N과 M (2) : 중복 미허용

private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
private static int N;
private static int M;
private static int[] nums; // 선택할 숫자들을 넣어둘 배열
private static int[] subset; // 선택한 숫자들을 넣어둘 배열

public static void main(String[] args) throws IOException {

    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    nums = new int[N];
    subset = new int[M];
    for(int i=1; i<=N ; i++) nums[i-1] = i;

    Combination(0, 0);

    bw.close();
}

private static void Combination (int cnt, int k) throws IOException {
    // 만약 목표한 개수(M)만큼 도달하면 -> subset에 숫자가 가득 찼으므로 -> BufferedWriter에 저장
    // 이때, 문제의 형식상 숫자를 차례대로 공백으로 구분해서 입력하고, 한 줄의 수열이 끝날때마다 줄바꿈을 넣어준 것
    // 만약 괄호와 쉼표를 이용해 구분한다면, Arrays.toString()을 사용하면 된다.
    if (cnt == M) {
        for(int i = 0 ; i< M ; i++) bw.append(""+subset[i]).append(" ");
        bw.append("\n");
        return;
    }

    // 여기서 포인트는 k부터 시작되는 반복이라는 점이다.
    // 재귀를 통해 k값이 바뀌고, 해당 k가 주어진 숫자 N을 넘어가면, 재귀가 더이상 반복되지 않는다.
    for(int i = k ; i < N; i++) {
        subset[cnt] = nums[i];
        Combination(cnt + 1, i + 1);
    }
}

---

2. no15652 N과 M (3) : 중복 허용

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int N;
    private static int M;
    private static int[] nums;
    private static int[] subset;

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        nums = new int[N];
        subset = new int[M];
        for(int i=1 ; i<=N ; i++) nums[i-1] = i;

        Combination(0, 0);

        bw.close();
    }

    private static void Combination (int cnt, int k) throws IOException {
        if(cnt == M) {
            for(int i = 0 ; i<M ; i++) bw.append(""+subset[i]+" ");
            bw.append("\n");
            return;
        }

        for(int i = k; i<N ; i++) {
            subset[cnt] = nums[i];
            Combination(cnt+1, i);  // 중복을 허용하는 경우
//            Combination(cnt + 1, i + 1); // 중복을 허용하지 않는 경우
        }
    }

---

Chat GPT 코드