[Java] 백준 3040번: 백설 공주와 일곱 난쟁이

문제

일단 생각하기!

• 백준 2309번 일곱 난쟁이와 아주 유사한 문제로 이 문제는 답이 유일하여 더욱 간단하다.
• 9명의 난쟁이 중 진짜 난쟁이 7명을 찾아야하므로 순서가 필요 없는 조합 문제이다. 재귀를 통한 조합을 이용하여 합이 100이 되는지 확인 후 출력했다.
• 하지만 전날 풀어봤음에도 어느 부분이 틀렸는지 알아채지 못해 헤맸다. 아직 조합을 완벽하게 이해하고 있는 것이 아니므로 다시 제대로 공부하기!

풀이

package BJ;

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

/**
 * 
 * @author 김유나
 * 2023-08-11
 * 
 * [문제] 백준 3040번 백설공주와 일곱 난쟁이
 * - 2309번 일곱 난쟁이와 비슷한 문제인데 이 문제는 답이 유일하여 더욱 간단하다.
 * - 아홉명의 난쟁이 중 진짜 난쟁이 일곱명을 찾는 문제
 * [아이디어]
 * - 재귀를 이용한 조합으로 난쟁이 7명을 뽑고 모자 숫자의 합이 100이 되는지 확인한 뒤 출력한다.
 *
 * 메모리 : 14,044kb 실행 시간 : 124ms
 */
public class BJ_3040_백설공주와일곱난쟁이_김유나 {
	static int[] shortMan, real;
	static int sum;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		shortMan = new int[9];
		real = new int[7];
		
		for (int i = 0; i < 9; i++) {
			shortMan[i] = Integer.parseInt(br.readLine());
		}
		
		comb(0, 0, 0);
	}
	
	static void comb(int count, int start, int sum) {
		if (count == 7) {
			if (sum == 100) {
				for (int i = 0; i < 7; i++) {
					System.out.println(real[i]);
				}
				return;
			}
			return;
		}
		
		for (int i = start; i < 9; i++) {
			real[count] = shortMan[i];
			comb(count + 1, i + 1, sum + real[count]);
		}
	}
}