[JAVA]BOJ 15655, N과 M (6)

이 문제는 조합이다. 조합은 순서에 상관없이 N개에서 M개를 선택하는 수열이다. 1 7과 7 1은 같은 수열이다.

 

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] + 1;

    // 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이면, 중복없이 뽑기 위해 smallest = result[0] + 1 = 2을 저장한다. 

 

base case는 앞선 15654번과 같다. 출력한다.. 근데 result배열에는 arr의 인덱스를 저장한것이므로 arr[result[ ]] 형식으로 출력해야한다.

recursive case는 조금 다르다. recursive case를 실행하기 전에 smallest를 설정한다. 지금까지 선택한 값이 없으면(이번이 첫번째 선택) smallest = 0이다. 이전에 선택한 적이 있다면 마지막으로 저장한 수보다 + 1 을해 저장한다. 

그리고 반복문을 실행한다. 이는 오름차순으로 중복없이 정렬하기위해 설정된 값이다.

---

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

// 조합
public class BOJ15655 {
    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] + 1;

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