[JAVA] 백준 2309 일곱 난쟁이

조합으로 풀면 되는 간단한 문제이다!

그런데 한번 틀렸습니다가 떠서 뭐지 했는데

답이 여러개인 경우 여러개를 출력하는게 문제였다,,ㄱ- 답은 한개만 출력하면 되므로

flag를 사용해서 최종배열이 완성되었을때 더이상 탐색하지 않도록 해주었다.

 

해당반례>

input:

10

11

12

13

14

15

16

17

18

​

output:

10

11

13

15

16

17

18

또는

10

12

13

14

16

17

18

또는

11

12

13

14

15

17

18

 

<코드>

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

public class bj2309 {
	static boolean flag;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int[] nanjeng = new int[9];
		int[] result = new int[7];
		for (int i = 0; i < 9; i++) {
			nanjeng[i] = sc.nextInt();
		}

		Arrays.sort(nanjeng); //나중에 오름차순으로 출력하기 위함

		comb(0, 0, nanjeng, result); //조합
	}

	static void comb(int start, int cnt, int[] nanjeng, int[] result) {
		if (flag == true) { //최종 완성 되었는지를 확인 (답이 여러개일 시 이중출력 방지)
			return;
		}
		if (cnt == 7) { // 조합 완성
			int sum = 0;
			for (int i = 0; i < 7; i++) {
				sum = sum + result[i];
				if (sum > 100) { //합이 100을 넘어간 경우 미리 종료해줌
					return;
				}
			}
			if (sum == 100) { // 합이 100인 경우
				flag = true; // 최종 완성 되었으므로 true로 변경
				for (int i = 0; i < 7; i++) {
					System.out.println(result[i]);
				}
			}
			return;
		}

		for (int i = start; i < 9; i++) {
			result[cnt] = nanjeng[i]; 
			comb(i + 1, cnt + 1, nanjeng, result);
		}

	}
}