[JAVA]BOJ 15657, N과 M (8)

중복가능, 비내림차순 = 오름차순 --> 중복 조합이다.

 

1. 메인 --> 입력받고 오름차순 정렬함

2. printSequence 함수

public static void printSequence(int[] arr, int[] result, int N, int M, int toPick){
    int i, lastIdx, smallest;

    // base case -> 다 뽑았을때
    if (toPick == 0){
        for(i=0;i<M;i++)
            System.out.print(arr[result[i]] + " ");
        System.out.println();
        return;
    }

    // 결과배열의 idx, 초기에는 -1
    lastIdx = M - toPick - 1;

    // 반복문 돌릴때 i의 최소값 정하기
    if(toPick == M)
        smallest = 0;
    else
        smallest = result[lastIdx]; // 중복선택 가능하게 최솟값 변경

    // recursive case
    for(i=smallest;i<N;i++){
        result[lastIdx + 1] = i;
        printSequence(arr, result, N, M, toPick - 1);
    }
}

lastIdx : 결과 배열(result)의 인덱스 번호

smallest : 오름차순 정렬을 위해 사용한다. 단, 중복선택이 가능해야 하므로 최솟값을 마지막에 선택한 값 그 자체로 설정한다. 예를 들면, 마지막으로 저장한 수가 'result[0] = 1'이면, 다음으로 선택 가능한 수들 중에 제일 작은 수는 '1'이다. (조합일땐 +1을 해줘야함)

base case설명은 생략.. 앞이랑 같다.

recursive case에서 조합문제(15655번)과 다른점은 없다.

 

중복조합과 조합의 차이는 당연하지만 중복이 되지않는다는거다. 조합에서는 중복이 되지 않도록 smallest를 '마지막으로 선택한 값 +1'로 정해주고, 중복조합은 마지막에 '선택한 값' 그 자체로 정한다.

---

아래는 전체 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

// 중복조합
public class BOJ15657 {
    public static void printSequence(int[] arr, int[] result, int N, int M, int toPick){
        int i, lastIdx, smallest;

        // base case -> 다 뽑았을때
        if (toPick == 0){
            for(i=0;i<M;i++)
                System.out.print(arr[result[i]] + " ");
            System.out.println();
            return;
        }

        // 결과배열의 idx, 초기에는 -1
        lastIdx = M - toPick - 1;

        // 반복문 돌릴때 i의 최소값 정하기
        if(toPick == M)
            smallest = 0;
        else
            smallest = result[lastIdx]; // 중복선택 가능하게 최솟값 변경

        // recursive case
        for(i=smallest;i<N;i++){
            result[lastIdx + 1] = i;
            printSequence(arr, result, N, M, toPick - 1);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, M, i;
        int[] arr, result;
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];
        result = new int[M];

        // 입력
        st = new StringTokenizer(br.readLine());
        for(i=0;i<N;i++)
            arr[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(arr); // 정렬
        printSequence(arr, result, N, M, M);
    }
}