[이때안] 조합(Combination) 예제로 익히기 | 그릇 만들기

재료가 N개 있을 때, M개의 재료로 그릇을 만든다고 했을 때 만들 수 있는 그릇의 종류를 구하라.

만약 재료가 A A B C C 일 때,

[A, A]

[A, B]

[A, C]

[B, C]

[C, C]

총 5가지 종류의 그릇을 만들 수 있다.

이 문제의 경우 기본적으로 조합을 이용하는 것이고, N개의 재료 중 같은 종류의 재료로 [A, A]라는 조합을 만들어 낼 수 있지만 하나의 B로 [B,B]와 같은 조합은 허용하지 않으므로 중복 조합이 아닌 단순 '조합'을 이용해야 한다.

---

조합의 기본 형태

public class nmSol {
	
    static int[] model;
    static int N, M;
	
    public static void combination(int startInd, int depth) {
        // 4개 중 2개 뽑는다. [1,2] [2,1]은 서로 같은 거
        if(depth == M) {
            for(int i = 0; i < M; i++) {
                System.out.print(model[i]);
                System.out.print(" ");
            }
            System.out.println();
            return;
        }

        for(int i = startInd; i < N; i++) {
            model[depth] = i + 1;
            combination(i + 1, depth + 1); // startInd가 그 이전 i보다 작으면 안되기 때문에 i+1을 넘겨줌
        }
    }

    public static void main(String[] args) throws Exception {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            model = new int[M];

            // 조합
            combination(0,0);
    }
}

 

그릇 만들기 전체 코드

import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Main {
	static int[] materials;
	static int[] combi;
	static Set<List<Integer>> allList = new HashSet<>();
	static int choose;
	
	public static void combination(int startIdx, int depth) {
		if(depth == choose) {
			List<Integer> bowlList = new ArrayList<>();
			for(int z = 0; z < combi.length; z++) {
				bowlList.add(combi[z]);
			}
			allList.add(bowlList);
			return;
		}
		
		for(int i = startIdx; i < materials.length; i++) {
			combi[depth] = materials[i];
			combination(i + 1, depth + 1);
		}
		
	}
	
	public static void main(String[] args) throws Exception {
		int TC;
		
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		 
		TC = sc.nextInt();
		for(int i = 0; i < TC; i++) {
			int N = sc.nextInt();
			choose = sc.nextInt();
			materials = new int[N];
			combi = new int[choose];
			allList.clear();
			
			for(int j = 0; j < N; j++) {
				materials[j] = sc.nextInt();
			}

			Arrays.sort(materials);
			combination(0,0);
			
			System.out.println(allList);
			System.out.println("#" + i + " " + allList.size());
		}
		
	}

}

 

1. 주어진 인풋들을 이용해 변수들을 초기화한다.
materials엔 주어진 재료들이 들어가는데 조합 후 중복을 제거하기 위해 Arrays.sort로 정렬해준다. 

* int[] 형은 Arrays.sort()를 사용한다.

ex) [1,3,1] [1,1,3]은 같은 조합인데 재료를 초반에 정렬해 두지 않으면 다른 조합으로 인지하게 된다.

 

2. combination(0,0)을 시작으로 조합을 시작한다.

public static void combination(int startIdx, int depth) {
    if(depth == choose) {
        List<Integer> bowlList = new ArrayList<>();
        for(int z = 0; z < combi.length; z++) {
            bowlList.add(combi[z]);
        }
        allList.add(bowlList);
        return;
    }

    for(int i = startIdx; i < materials.length; i++) {
        combi[depth] = materials[i];
        combination(i + 1, depth + 1);
    }

}

 

combi에는 재료의 조합이 생성되어 저장된다.

combi는 int[] 이기때문에 M개로 크기가 지정되어 있어서 인덱스 값만 지정해 값을 할당한다. 만약 combi가 List로 선언된 경우 지정된 크기가 없어 조합이 완성될 때마다 끝에 추가된 재료를 빼가며 관리해야 한다.

 

따라서 크기를 지정할 수 있다면 int[]로 선언하여 쓰는 것이 훨씬 편하다 !!

 

3. allList에는 중복된 조합이 저장될 수 없으므로 allList.size()를 출력한다.

재료 정렬 후 1 1 2 3 3 에서 2개를 뽑는 것으로 조합을 했을 때 [1,3] [1,3] 이렇게 나올 수 있다.

Set<List<Integer>> allList = new Hashset<>(); 으로 선언하여 중복된 것이 저장될 수 없도록 한다.