[백준] 2309. 일곱 난쟁이 - 브론즈2

https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

 

문제 요약

9명의 난쟁이 키가 입력으로 주어지면, 합이 100이 되는 일곱 난쟁이를 찾아내야 한다.

 

 

문제 해결 아이디어

입력 크기가 크지 않으므로 모든 경우를 검사해 보는 완전탐색 기법을 생각했다.

1. 9명 중에 7명을 뽑는다. 순서는 중요하지 않기 때문에 조합으로 생각했다.
2. 뽑힌 7명의 합을 구해 100과 비교한다
3. 100이면 출력

 

완성된 코드

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

public class Main_BOJ_2309_일곱난쟁이 {
	static int[] input;
	static int[] results;

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

		input = new int[9];
		results = new int[7];

		for (int i = 0; i < 9; i++)
			input[i] = Integer.parseInt(br.readLine());

		solve(0, 0);
	} // end of main

	private static void solve(int cnt, int start) {
		// 9명 중에 7명을 뽑는 조합
		StringBuilder sb = new StringBuilder();

		if (cnt == 7) {
			int sum = 0;
			for (int i = 0; i < 7; i++)
				sum += results[i];
			if (sum == 100) { // 합계가 100인 조합 출력
				Arrays.sort(results); // 오름차순 정렬
				for (int i = 0; i < 7; i++)
					sb.append(results[i]).append("\n");
			}
			System.out.print(sb);
			return;
		}

		for (int i = start; i < 9; i++) {
			results[cnt] = input[i];
			solve(cnt + 1, i + 1);
		}
	}
}// end of class