[백준/boj] 3040: 백설 공주와 일곱 난쟁이 (Java) / 조합

문제

3040번: 백설 공주와 일곱 난쟁이

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static int[] capNum;
	static boolean[] isSelected;
	static int[] nums = new int[7];
	// 9C7 조합
	
	public static void main(String[] args) throws IOException {
		capNum = new int[9];
		for(int i=0 ;i < 9; i++) {
			capNum[i] = stoi(br.readLine());
		}
		combination(0,0);
	}
	
	private static void combination(int cnt, int start) {
		if(cnt == 7) {
			int total = 0;
			for(int i=0 ; i< nums.length; i++)
				total += nums[i];
			if(total == 100) {
				for(int i=0 ; i< nums.length; i++)	
					System.out.println(nums[i]);	
			}
			return;
		}
		
		for(int i= start; i< capNum.length; i++) {
			nums[cnt] = capNum[i];
			combination(cnt+1, i+1);
		}
	}
	
	public static int stoi(String input) {
		return Integer.parseInt(input);
	}
}

 

아홉명의 난쟁이 중 7명의 진짜 난쟁이(모자의 수가 합쳐서 100)를 찾아야 하므로 9명중 7명을 뽑는 조합 ! (무작위로 뽑기 때문에 순서가 상관 없음) 을 사용해야한다. 

재귀를 사용해서 combination이 뽑힐 때마다 cnt 와 start를 1씩 증가시켜 중복을 피하도록 했다.

이때 주의할 점은
1. start+1 이 아닌 i+1 을 해야한다는 점이고( 뽑인 인덱스 기준으로 다음 인덱스부터 뽑아야하기 때문)
2. cnt++ 이 아닌 cnt +1을 한다는 점이다. cnt 자체를 변경시키면 한개의 조합만 나온다.

cnt가 7이 되었다는 것은 7 명을 뽑았다는 것을 의미하기 때문에 다 더하고, 더한 값이 100이면 출력하도록 했다.