[백준] 백설 공주와 일곱 난쟁이(자바)

• 문제 방안 도출 : 아홉 난쟁이 중에서 총합이 100이 되는 일곱 난쟁이를 찾는 문제이므로, 모든 경우의 수를 확인해야한다고 생각했다. 따라서, 이와 관련된 알고리즘인 브루트포스 알고리즘을 도출할 수 있었다.
• 접근 유형 : 브루트포스 알고리즘
• 브루트포스 알고리즘
  • 모든 경우의 수를 탐색하면서 조건에 만족하는 결과를 찾는다.
  • 이와 같은 알고리즘은 for문, 재귀, DFS, BFS 등을 사용하여 해결할 수 있다.

 

package com.algorithm.boj;

import java.util.Scanner;

/*
 * 일곱난쟁이들의 모자 합은 100이 되어야함
 * 접근 유형 : 브루트포스 알고리즘
 * */

public class Main_3040 {
	
	private static int[] hat;
	private static int size;
	private static boolean[] visited;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		size = 9;
		hat = new int[size];
		
		for(int i = 0; i < size; i++) {
			hat[i] = sc.nextInt();
		}
		
		visited = new boolean[size];
		
		for(int i = 0; i < size; i++) {
			search(0, i, 0);
		}
		
		
		sc.close();
	}

	/**
	 * @param count 뽑는 횟수
	 * @param start 선택한 번호
	 * @param sum 합
	 */
	public static void search(int count, int start, int sum) {
		if(count == 7 && sum == 100) {
			for(int i = 0; i < size; i++) {
				if(visited[i])
					System.out.println(hat[i]);	
			}
			return;
		}
		if(count == 7) return;
		
		//모든 경우에 대해 탐색하기 위해
		for(int i = start; i < size; i++) {
			if(!visited[i])
				visited[i] = true;
			search(count+1, i+1, sum+hat[i]);
			visited[i] = false;
		}
		return;
	}
	
}