[백준] 2309. 일곱 난쟁이 (Java)

 

🔒 문제

2309번: 일곱 난쟁이

 

🔑 알고리즘

조합, 정렬

 

 

 

💡  풀이

9명의 정수 중 합이 100이 되는 7개의 정수를 찾는 문제이다.

난쟁이의 순서는 의미 없기 때문에 9명 중 순서 상관 없이 7명을 뽑는 조합으로 문제를 해결하였다.

키를 오름차순으로 출력해야하기 때문에 난쟁이들의 키 리스트를 미리 오름차순으로 정렬하였다.

 

 

 

✏️ 코드

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

public class Main {
	static int[] arr;
	static boolean[] selected;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		arr = new int[9];
		selected = new boolean[9];
		for(int i=0; i<9; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		Arrays.sort(arr);
		comb(0, 0);
	}

	static void comb(int count, int start) {
		if(count == 7) {
			int sum = 0;
			for(int i=0; i<9; i++) {
				if(selected[i]) {
					sum += arr[i];
				}
			}
			if(sum == 100) {
				for(int i=0; i<9; i++) {
					if(selected[i]) {
						System.out.println(arr[i]);
					}
				}
				System.exit(0);
			}
			
			return;
		}
		
		
		for(int i = start; i<9; i++) {
			if(!selected[i]) {
				selected[i] = true;
				comb(count +1, i);
				selected[i] = false;
			}
		}
	}
}