백준 2309 <일곱 난쟁이>

총 9명의 난쟁이 중에 7명을 선택 하는 조합 문제이다.

 

간단하게 조합을 알고 있다면 금방 해결할 수 있는 문제이다.

 

문제 해결 순서

1. 난쟁이들을 키순서대로 정렬
2. 9명의 난쟁이로 7명의 난쟁이를 선택한다.
3. 난쟁이의 키가 100이 된다면 return

또한 7명의 난쟁이를 선택하는 경우 == 전체의 난쟁이 중 2명을 빼는 경우이기 때문에 반대로도 해결이 가능하다.

 

전체 코드

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class Main{

	static int num[], result[];
	static boolean flag = true;
	static StringBuilder s = new StringBuilder();

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		num = new int[9];
		result = new int[7];
		for (int i = 0; i < 9; i++) {
			num[i] = kb.nextInt();
		}
		go(0, 0);
		Arrays.sort(result);
		for (int i = 0; i < 7; i++)
			System.out.println(result[i]);
	}

	public static void go(int index, int start) {
		if (index == 7) {
			if (cal()) {
				flag = false;
			}
			return;
		}
		for (int i = start; i < 9; i++) {
			result[index] = num[i];
			go(index + 1, i + 1);
			if (flag == false) {
				return;
			}
		}

	}

	public static boolean cal() {
		int sum = 0;
		for (int i = 0; i < 7; i++) {
			sum += result[i];
		}
		if (sum == 100) {
			return true;
		}
		return false;
	}

}