[백준] 2309번 : 일곱난쟁이 - 자바(JAVA)

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

2309번: 일곱 난쟁이

 

문제 해석

조합 문제로 9C7 == 100을 찾는 문제

정답이 여러 개 존재할 수 있어서 한 개만 출력해야 하는 것과 정렬해주는 것만 주의하면 됩니다.

 

코드

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

public class Main_2309_일곱난쟁이 {

	static int[] heights = new int[9];
	static int[] answers = new int[7];
	static boolean flag;

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

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

		combination(0, 0, 0);

	}

	private static void combination(int num, int start, int sum) {

		// 수식 하나 완성후에는 더이상 탐색x
		if (flag) {
			return;
		}

		// 100 넘으면 탐색x
		if (sum > 100) {
			return;
		}

		if (num == 7) {

			// num==7인경우에만 100을 탐색해야한다.
			if (sum != 100) {
				return;
			}

			Arrays.sort(answers);
			StringBuilder sb = new StringBuilder();
			for (int e : answers) {
				sb.append(e + "\n");
			}
			System.out.print(sb.toString());
			flag = true;
			return;
		}

		for (int i = start; i < 9; i++) {

			answers[num] = heights[i];
			sum += heights[i];
			combination(num + 1, start + 1, sum);
			sum -= heights[i];
		}

	}

}