2309_일곱난쟁이

-문제

 

-접근

아홉명 중 일곱명을 뽑은 경우의 수를 모두 탐색한다. => 브루트포스

이중 for문을 사용

 

-내 풀이

#include<stdio.h>
#include<stdlib.h>
int compare(const void *a, const void *b)    // 오름차순 비교 함수 구현
{
    int num1 = *(int *)a;    // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴
    int num2 = *(int *)b;    // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴

    if (num1 < num2)    // a가 b보다 작을 때는
        return -1;      // -1 반환
    
    if (num1 > num2)    // a가 b보다 클 때는
        return 1;       // 1 반환
    
    return 0;    // a와 b가 같을 때는 0 반환
}
int main(void){
	int arr[9]={0};
	int i,k,total=0;
	bool exitOutLoop=false;
	
	for(i=0;i<9;i++){
		scanf("%d",&arr[i]);
		total+=arr[i];
	}
	
	qsort(arr,sizeof(arr)/sizeof(int),sizeof(int),compare);

	for(i=0;i<9;i++){
		for(k=0;k<9;k++){
			if(i!=k){
				if(100==total-arr[i]-arr[k]){
					exitOutLoop=true;
					break;
				}
			}
		}
		if(exitOutLoop==true)
			break;
	}
	
	for(int j=0;j<9;j++){
		if(j!=i&&j!=k)
			printf("%d\n",arr[j]);
	}
	
	return 0;
}

 

-해설참고

9C7 조합을 하는 경우로 풀면된다.

c++ 내장함수에 permutation(), 즉 순열을 구하는 함수가 있다.

n의 개수가 크지 않으므로 순열 내장함수를 이용해 문제를 푼다.

 

#include<bits/stdc++.h>
using namespace std;
int i,a[9];
int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);
    
    for(i=0;i<9;i++){
    	cin >> a[i];
	}
	sort(a,a+9); //permutation 함수에 정렬 후 삽입
	
	do{
		int sum=0;
		for(i=0;i<7;i++) sum+=a[i];
		if(sum==100) break;
	}while(next_permutation(a,a+9));
	
	for(i=0;i<7;i++) cout<< a[i]<<"\n";
	return 0;
	
}