BOJ_3040_백설 공주와 일곱 난쟁이

1. 

구분: 브루트포스 알고리즘

언어: java

전략

• 조합을 통해 9명의 난쟁이 중 7명의 난쟁이를 고른다
• 각 모자의 합이 100인 난쟁이 조합이 답이다 

---

2. 코드

import java.util.Scanner;

public class BOJ_3040 {
	
	private static int[] hat, real;
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		hat = new int[9];
		real = new int[7];
		for(int i = 0; i<9; i++) {
			hat[i] = scanner.nextInt();
		}
		comb(0,0,0);
		
	}
	
	private static void comb(int start, int cnt, int sum) {
		//가지치기 - 이미 7명이 아닌데 100이 넘어가면 그냥 더 볼 필요도 없음
		if(cnt<7 && sum >100)return;
		
		//7명 다 모았을 떄
		if(cnt ==7) {
			//합이 100이다 == 오리지널 난쟁이다 
			if(sum ==100) {
				for(int i = 0; i<7; i++)
					System.out.println(real[i]);
			}
			return;
		}
			
		//조합
		for(int i = start; i<9; i++) {
			real[cnt] = hat[i];
			comb(i + 1, cnt +1, hat[i] + sum);
		}
	}
}

 

---

3.

• 기본적인 조합 문제 
• 조합에서 매개변수에 바로 모자의 합을 구해서 가지치기(pruning)를 할 수 있었다. --> 7명을 아직 뽑지 않았는데 합이 이미 100을 넘어버리면 원하는 조합이 아님