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

Java

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

문제

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

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

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

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

접근 방법

9명의 난쟁이 중 7명을 조합으로 뽑는다.
뽑은 7명의 난쟁이 값이 100이면 출력한다.

구현

DFS의 조합 구현을 통하여 난쟁이를 뽑는다.
뽑은 7명의 난쟁이의 값을 매번 더하는 불필요한 작업을 피하기위해, 난쟁이를 뽑을 때 마다 DFS 매개변수로 합을 전달하여 7명 뽑았을 때 매개변수 값이 100인지 확인한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int[] sel, num;
	static boolean[] vsi;
    public static void main(String []args) throws IOException {        
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	num = new int[9];		// 9명의 난쟁이 값
    	sel = new int[7];		// 뽑은 7명의 난쟁이 값
    	vsi = new boolean[9];	// 선택 여부 확인
    	
    	for(int i = 0; i < 9; i++) {
    		num[i] = stoi(br.readLine());
    	}
    	
    	DFS(0,0,0);
    	
    	br.close();
    }
    // 9개 중에 7개를 뽑는 중복을 허용하지 않은 조합을 구한다. 9C7
    static void DFS(int lv, int sum, int start) {
    	if(lv == 7) {
    		// 7개 값의 합이 100이면 출력한다.
    		if(sum == 100) {
    			for(int v : sel) {
    				System.out.println(num[v]);
    			}
    		}
    		return;
    	}
    	for(int i = start; i < 9; i++) {
    		if(!vsi[i]) {
    			vsi[i] = true;
    			sel[lv] = i;
    			DFS(lv + 1, sum + num[i], i + 1);
    			vsi[i] = false;
    		}
    	}
    }
    
    
    static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐⭐★★★

후기

문제 조건인 행/열 최소 값은 2의 배수이다를 읽지 않아, 쓸데없이 고생했다.
문제를 잘 읽어라는 교수님 말씀이 뭔지 새삼 깨닫게된다 정말로,,

개선할 점

문제 좀 읽자!!!!