[백준] 3040번 : 백설 공주와 일곱 난쟁이 - 자바(JAVA)

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

3040번: 백설 공주와 일곱 난쟁이

문제 해석

일곱 난쟁이의 모자의 합은 100이다

그런데 갑자기 아홉 난쟁이가 등장하여 각자 자신이 진짜라고 우기는 상황이다.

이때 모자의 합을 통해 진짜 난쟁이가 누구인지 판별하라

모든 숫자는 서로 다르고, 답이 유일한 경우만 입력으로 주어진다.

 

문제 풀이 전 설계

N의 크기가 9이며 조합을 통한 완전 탐색으로 해결합니다.

9C7을 통해 7명의 난쟁이를 뽑고 모자의 합이 100이라면 출력합니다.

 

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

public class Main_3040_백설공주와일곱난쟁이 {

	static int[] hatsNum;
	static int[] sevenDwarfs = new int[7];
	static StringBuilder sb= new StringBuilder();
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		hatsNum = new int[9];
		for(int i=0; i<9; i++) {
			hatsNum[i] = Integer.parseInt(br.readLine());
		}
		combination(0,0);		
	}
	
	private static void combination(int cnt, int start) {
		if(cnt==7) {			
			if(isSumHundred()) {
				System.out.println(sb);
			}
			return;
		}
		
		for(int i=start; i<hatsNum.length; i++) {			
			sevenDwarfs[cnt] = hatsNum[i];
			combination(cnt+1, i+1);
		}
	}
	
	private static boolean isSumHundred() {
		int sum =0;
		sb = new StringBuilder();
		for(int i : sevenDwarfs) {
			sum+= i;
			sb.append(i + "\n");
		}
		if(sum!=100) {
			sb = new StringBuilder();
			return false;
		}
		
		return true;

	}
	
}