[Java] 백준 2309번: 일곱 난쟁이

문제

일단 생각하기!

• 9명의 난쟁이 중 7명을 뽑아 키의 합이 100이 되는지 구해야하므로 순서가 중요하지 않은 조합 문제다.
• 다만, 문제에서 여러 경우가 있을 경우 아무거나 출력하라 하였으니 합이 100이 되는 조합이 한번만 출력되도록 해야한다. 이때 flag 변수를 사용하여 출력이 됐는지 체크해준다.
• 또는 한번 출력된 후 시스템을 강제 정상 종료시키는 System.exit(0)을 사용하는 방법도 생각해보았다. 여담으로 System.exit(1)은 비정상 종료라고 한다. 백준에서 찾아보니 사용해도 아무 상관없다고는 하나 두가지 방법을 모두 알아봐야겠다!

풀이

package BJ;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 
 * @author 김유나
 * 2023-08-10
 * [문제] 백준 2309번 일곱 난쟁이
 * - 아홉명의 난쟁이 중 진짜 난쟁이 일곱명을 찾아라. 이때, 일곱 난쟁이의 키의 합이 100이다.
 * [아이디어]
 * - 아홉명의 난쟁이 중 일곱명을 뽑아야하므로 순서가 필요없는 조합 문제다.
 * - 다만, 여러 조합이 있을 경우 아무 경우만 출력하고 끝내야하므로 flag를 사용하여 한번 출력되면 끝나도록 한다.
 * 메모리 : 17,648kb, 실행 시간 : 216ms
 * 
 */
public class BJ_2309_일곱난쟁이_김유나 {
	static int height[], real[], flag = 0, sum = 0;
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		height = new int[9]; // 아홉명의 난쟁이들
		real = new int[7]; // 일곱명의 진짜 난쟁이들
		
		for (int i = 0; i < 9; i++) {
			height[i] = s.nextInt(); // 아홉명의 난쟁이들의 키
		}
		
		comb(0, 0, 0);
	}
	
	static void comb(int count, int start, int sum) {
		if (flag == 1) return; // 이미 출력이 됐다면 바로 return
		if (count == 7) { // 일곱 명을 뽑았고
			if (sum == 100) { // 100이라면
				flag++; // 처음 출력 시 flag++
				Arrays.sort(real); // 오름차순 정렬
				for (int i = 0; i < 7; i++) {
					System.out.println(real[i]);
				}
				// flag 대신 System.exit(0)를 써도 되는지?
			}
			return;
		}
		
		for (int i = start; i < 9; i++) {
			real[count] = height[i];
			comb(count + 1, i + 1, sum + real[count]);
		}
	}
}