[BOJ 2309] 일곱 난쟁이

문제

• BOJ 2309
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

9명의 일곱난쟁이 중 7명을 뽑으면서 각 합이 100이 되는 경우 뽑기를 중단하도록 조합함수를 작성해주었다. 작은 수부터 차례대로 더해주기 위해서 난쟁이를 배열에 입력받은 후 오름차순 해주었고, 조합은 재귀를 통해 해결했다.

코드

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

//일곱난쟁이
public class Main {
	
	static final int SUM = 10; //상수
	static int[] arr = new int[9]; //아홉난쟁이 키 배열
	static boolean[] visited = new boolean[9];
	static int[] result = new int[7]; //뽑은 난쟁이
	static boolean isFind = false;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for(int i=0; i<9; i++) {
			int height = Integer.parseInt(br.readLine()); //키
			arr[i] = height;
		}
		Arrays.sort(arr); //오름차순
		//조합 시작
		select(0, 0, 0);
	}
	
	static void select(int cnt, int start, int sum) { //뽑은 개수, 시작점, 키 합
		if(cnt == 7) { //일곱난쟁이를 모두 뽑았다면
			if(sum == 100) { //뽑은 일곱명의 키 합이 100이면
				isFind = true;
				for(int e : result) System.out.println(arr[e]);
				return;
			}
			return;
		}
		for(int i=start; i<9; i++) {
			if(sum>100) return;
			if(!visited[i]) {
				result[cnt] = i; //i번째 난쟁이 뽑음
				visited[i] = true; 
				sum += arr[i]; //키를 누적시키자
				select(cnt+1, i+1, sum);
				visited[i] = false;
				sum -= arr[i];
				if(isFind) break;
			}
		}
	}
}