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

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

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

문제

매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱개, 접시 일곱개, 나이프 일곱개를 준비한다.

어느 날 광산에서 아홉 난쟁이가 돌아왔다. (왜 그리고 어떻게 아홉 난쟁이가 돌아왔는지는 아무도 모른다) 아홉 난쟁이는 각각 자신이 백설공주의 일곱 난쟁이라고 우기고 있다.

백설공주는 이런 일이 생길 것을 대비해서, 난쟁이가 쓰고 다니는 모자에 100보다 작은 양의 정수를 적어 놓았다. 사실 백설 공주는 공주가 되기 전에 매우 유명한 수학자였다. 따라서, 일곱 난쟁이의 모자에 쓰여 있는 숫자의 합이 100이 되도록 적어 놓았다.

아홉 난쟁이의 모자에 쓰여 있는 수가 주어졌을 때, 일곱 난쟁이를 찾는 프로그램을 작성하시오. (아홉 개의 수 중 합이 100이 되는 일곱 개의 수를 찾으시오)

입력

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

출력

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

풀이 설명

1. 어떤 배열의 조합을 구하여 푸는 문제이다.

2. 9개의 입력을 받아 all 배열에 저장하고, 그 중 7개를 골라 그 합이 100이 되는지만 체크하면 된다.

3. 조합을 구하는 메소드 combination을 정의한다.

  3-1. 매개변수로 start와 현재 위치 current를 넘긴다. start는 하나를 고르고 다음 하나를 고를 때, all배열의 어디부터            탐색할 것인지 정해주고, current에는 현재 몇개를 골랐는지 저장한다.

  3-2. all의 start부터 끝까지 탐색하며 temp의 current 위치에 all의 현재 원소를 저장하고, start에 다음 위치, current는          1을 더하여 combination함수를 재귀호출한다.

  3-3. 뽑고싶은 개수만큼 다 뽑았다면, 지금까지 뽑은 원소들의 값을 다 더한 다음, 100이면 seven 배열에 복사한다.

Java 코드

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

public class Main {
	
	static int[] all;
	static int[] seven;
	static int[] temp;
	static int r = 7;
	
	public static void combination(int start, int current) {
		if(current == r) {
			int sum = 0;
			for(int i=0; i<temp.length; i++)
				sum += temp[i];
			if(sum == 100)
				seven = Arrays.copyOf(temp, r);
			return;
		}
		for(int i=start; i<all.length; i++) {
			temp[current] = all[i];
			combination(i+1, current+1);
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		all = new int[9];
		seven = new int[r];
		for(int i=0; i<9; i++)
			all[i] = Integer.parseInt(br.readLine());
		
		temp = new int[r];
		combination(0, 0);
		
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<seven.length; i++)
			sb.append(seven[i]).append("\n");
		System.out.println(sb);
	}
}