/ BOJ

BOJ_2309_일곱난쟁이_JAVA

문제 : 일곱난쟁이

링크 : BOJ_2309_일곱난쟁이

접근 방식

9명의 일곱난쟁이 중 7명을 골라 7명의 키의 합이 100이면 해당하는 7명의 난쟁이의 키를 오름차순으로 출력해야한다.

9명중에 7명을 고른다, 키를 비교하는 것이기 때문에 순서는 상관이 없다. 조합문제임을 유추할 수 있다.

조합의 경우의 수를 구하는 재귀 로직을 만들어 기저조건에서 노드의 합이 100인 경우를 찾으면 된다.

풀이 방법

  1. 멤버변수로 읽어올 input을 저장할 배열, 그리고 7개 골라서 저장할 배열 2개를 선언한다.

  2. 재귀를 이용해 9개중 7개를 고르는 조합을 구현한다. 기저조건에서 저장된 배열의 값을 모두 더한다.

  3. 저장된 배열의 합이 100이라면 check를 true로 바꾸고 해당하는 배열을 정렬하여 출력한다. 한번만 출력해야 하기 때문에 check가 true일 경우에는 더 이상 작동하지 않도록 조건에 추가한다.

소스 코드


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

public class BOJ_2309_일곱난쟁이 {
	static int[] nan;
	static int[] arr;
	static boolean check = false;
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		arr = new int[9];

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

		nan = new int[7];
		Arrays.sort(arr);

		combination(0,0);

	}

	public static void combination(int cnt, int start) {
		if(cnt == 7) {
			int sum = 0;
//			System.out.println(Arrays.toString(nan));
			for(int i=0;i<7;i++) {
				sum += nan[i];
			}
			if(sum == 100 && !check) {
				check = true;
				Arrays.sort(nan);
				for(int i=0;i<7;i++) {
					System.out.println(nan[i]);
				}
			}
			return;
		}

		for(int i=start;i<9;i++) {
			nan[cnt] = arr[i];
			combination(cnt+1, i+1);
		}


	}

}

}