백준 2309 일곱 난쟁이 JAVA

백준 3040번 백설공주와 일곱 난쟁이와 굉장히 유사한 문제라고 생각해서 "개꿀이당 ㅎㅎ" 이러고 풀었다가
호되게 당한 문제...
맞왜틀!!!!!!! 맞왜틀!!!!! 을 외치며 30분동안 더 고민하게 한 문제였다.
채점중 97%에서 자꾸 틀려서 진짜 답답했는데 반례를 보자마자 고개를 끄덕였던 문제..

풀이 방법

1. 10명의 난쟁이 中 7명을 순서 상관 없이 뽑아야 한다는 조건에서 '조합'으로 풀어도 되는 문제라고 생각

2. 10개의 입력을 배열1로 받고

3. 10C7 연산을 실행

4. 생성된 새로운 배열2의 값들의 합이 100인지 확인

5-1. 100 이라면 -> 정답 처리 

#중요# 10개중에 7개의 합이 100이 되는 다른 경우가 또 출력되지 않도록 isEnd = true로 변경시켜주기 

5-2. 100이 아니라면 -> pass

 

package algorithm;

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

public class BOJ_B2_2309_일곱난쟁이 {
	static int[] hats;
	static boolean[] visited;
	static int N = 9; // 총 9명의 난쟁이 입력
	static boolean isEnd = false;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		hats = new int[9];
		visited = new boolean[9];
		
		for(int i=0; i<N; i++) {
			hats[i] = Integer.parseInt(br.readLine());
		}
		
		comb(hats, visited, 0, 9, 7);

	}
	
	// 재귀 사용
	// 사용 예시 : comb(arr, visited, 0, n, r)
	static void comb(int[] arr, boolean[] visited, int depth, int n, int r) {
		if (r == 0) {
			print(arr, visited, n);
			// 재귀종료시점에 할일 구현
			return;
		}

		if (depth == n) {
			return;
		}

		visited[depth] = true;
		comb(arr, visited, depth + 1, n, r - 1);

		visited[depth] = false;
		comb(arr, visited, depth + 1, n, r);
	}

	// 배열 출력
	static void print(int[] arr, boolean[] visited, int n) {
		int sum = 0;
		for (int i = 0; i < n; i++) {
			if (visited[i]) {
				sum += arr[i]; 
			}
		}
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		if(sum == 100) { // 일곱난쟁이 찾음
			for (int i = 0; i < n; i++) {
				if (visited[i]) {
					list.add(arr[i]);
				}
			}
		}
		if(!list.isEmpty() && isEnd == false) {
			Collections.sort(list);
			for(int i=0; i<list.size(); i++) {
				System.out.println(list.get(i));
			}
			isEnd = true;
		}
		
	}
}