[Java] Baekjoon3040: 백설 공주와 일곱 난쟁이

백설 공주와 일곱 난쟁이

1 초

128 MB

8628

5901

5035

70.538%

문제

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

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

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

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

입력

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

출력

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

풀이

브루트 포스 문제입니다. 조합을 이용해 9명 중 7명을 뽑아 더해서 100이 나올 때 그 수들을 선택하면 됩니다.

부분집합이므로 dfs를 이용한 풀이를 진행했습니다.

 

입력값 받기

Scanner sc = new Scanner(System.in);
int[] arr = new int[9];

for(int i=0; i<9; i++) {
    arr[i] = sc.nextInt(); //9 난쟁이의 수를 받아주기
}

 

반례 주의

난쟁이 7명이 차기 전에 100이 될 수도 있습니다.

또 난쟁이가 8명인데 합이 100이 나올 수도 있으므로 이런 경우를 주의해야합니다.

 

dfs 이용한 풀이

import java.util.*;

public class Main {
	static int[] answer = new int[7]; //7명의 난쟁이 선택
	static int[] arr = new int[9]; // 총 9명의 난쟁이 값을 받기
	
	static void dfs(int idx, int cnt, int sum) {
		if(idx==9) { //9에 도달하면 return으로 종료시켜야 합니다
        
			if(sum==100 && cnt==7) { //합이 100이면서 동시에 7명이라면 정답이므로 출력
				for(int i=0; i<7; i++) {
					System.out.println(answer[i]);
				}
			}
			return;
		}
        
		dfs(idx+1,cnt,sum); // 현재 난쟁이를 선택X
		
		if(cnt<7)answer[cnt]=arr[idx]; //8명을 넘게 선택한 경우 오류 발생
        
		dfs(idx+1,cnt+1,sum+arr[idx]); // 현재 난쟁이를 선택O
	}
	public static void main(String[] args){
	Scanner sc = new Scanner(System.in);	
	for(int i=0; i<9; i++) {
		arr[i] = sc.nextInt();
	}
	dfs(0,0,0); // 난쟁이 번호(0~9), 현재까지 선택한 난쟁이, 합
}
}