[백준(Baekjoon)] 3040. 백설 공주와 일곱 난쟁이

 

[백준(Baekjoon)] 3040. 백설 공주와 일곱 난쟁이

 

 

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

 

 

[입력]

 

총 아홉개 줄에 1보다 크거나 같고 99보다 작거나 같은 자연수가 주어진다. 모든 숫자는 서로 다르다. 또, 항상 답이 유일한 경우만 입력으로 주어진다.

 

 

[출력]

 

일곱 난쟁이가 쓴 모자에 쓰여 있는 수를 한 줄에 하나씩 출력한다.

 

 

 

[풀이]

 

조합을 구하는 문제이다.
9개 중 순서 상관없이 7개를 택하여 그 합이 100이 되는 것만 출력한다.
조합은 재귀를 이용해서 구현했다.

 

 

 

public class algo3040 {

	static int[] nine; //9개의 숫자를 담은 배열
	static int[] real; //진짜 일곱난쟁이의 숫자를 담은 배열
	static int N = 7;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		nine = new int[9];
		real = new int[7];
		
		for (int i = 0; i < 9; i++) {
			nine[i] = sc.nextInt();
		}
		
		comb(0,0);

	}
	
	public static void comb(int cnt, int start) {
		if(cnt == N) {
			int sum = 0;
			for (int i = 0; i < N; i++) {
				sum += real[i]; //7개를 뽑으면 그 숫자를 다 sum에 더해줌
			}
			if(sum == 100) { //합이 100이면 출력
				for (int r : real) {
					System.out.println(r);
				}
			}
			return;
			
		}
		
		for (int i = start; i < 9; i++) {
			real[cnt] = nine[i]; //real에 저장
			comb(cnt+1, i+1); //재귀로 뒤 숫자 뽑기
		}
		
	}

}

 

 

 

메모리	시간	언어	코드 길이
17692	216	Java 11	722