2309번 일곱 난쟁이

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주👸에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

아홉 명의 난쟁이 중에서 7명의 난쟁이의 합이 100 인것을 먼저 구해야함

브루트포스(brute force) : 난폭한 힘 => 완전탐색 알고리즘

선형구조를 전체적으로 탐색 -> 순차탐색

비선형 구조를 전체적으로 탐색
-> 깊이 우선 탐색(DFS, Depth First Search)
-> 너비 우선 탐색(BFS, Breadth First Search)

9개 중 7명의 키를 구하는 조합 문제가 아닌

아홉명의 난쟁이들의 키 - (특정 두명의 키) 의 조합이 100인것을 구함

1. 전체 sum을 구하여 나머지 2개를 뺌

int Soultion(int *arr) {
	int sum = Getsum(arr); // 전체의 sum 값을 구함
    
    	for(int i=0; i<8; i++) {
        	for(int j=i+1; j<9; j++) {
            if(sum - (arr[i]+arr[j]) == 100) }
            	arr[i] = -1
                arr[j] = -1
                return 0
                }
           }
   	 return -1
 }

2. 9명에서 2명을 뺀 조합을 구함

for (int i=0;i<8;i++) {
	int total = 0
    
    	for(int j=i+1;j<9;j++) {
        total = 0
        
        //나머지 7명의 값 저장
       	for(int k = 0, n = 0; n<9;n++) if(n!=i&&n!=j) result[n++] - num[n]
        // n++ 이유는 반복문 진행시 증가시켜야 배열에 순차대로 값이 들어감
        
    	    if(total == 100) break // 반복문1 나옴
 	if(total == 100) break // 반복문2 나옴
}