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

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

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

 

 

 

 

 

 

9명 중에서 7명을 찾는 것이므로 9C7 -> 조합 문제이다.

 

조합 7개를 다 완성하고 리턴하기 전에 조합의 합이 100이 되는지 확인해서 출력해주면 된다.

 

 

 

 

 

코드

import java.util.Scanner;

public class Main {
	static int[] hats;
	static boolean[] visited;
	static int[] result;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		hats = new int[9];
		
		for(int i = 0; i < 9; i++) {
			hats[i] = sc.nextInt();
		}
		
		visited = new boolean[9];
		result = new int[7];
		
		combination(0, 0);

	}

	public static void combination(int start, int depth) {
		if(depth == 7) {
			int sum = 0;
			
			for(int n : result) {
				sum += n;
			}
			
			if(sum == 100) {
				for(int n : result) {
					System.out.println(n);
				}
			}
			
			return;
		}
		
		for(int i = start; i < 9; i++) {
			if(visited[i]) continue;
			
			visited[i] = true;
			result[depth] = hats[i];
			combination(i + 1, depth + 1);
			visited[i] = false;
		}
	}
}

 

 

 

 

 

 

결과