[C++] 백준 2309번 일곱 난쟁이

 

1) 문제설명

백준 Online Judge 2309번 일곱 난쟁이

https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

 

2) 아이디어

이전에 설명한 조합과 순열을 사용해서 문제를 해결하였다.

입력된 배열을 오름차순으로 정렬한뒤

 

순열 :

9명의 난쟁이의 키를 입력받고 이를 순열로 인덱스를 바꾸면서 도는동안 난쟁이들의 키의 합이 100이 될 경우

반복문을 멈추고 그대로 앞에 저장된 배열을 출력하였다.

조합 : 

2중 for문을 돌면서 난쟁이의 키의 합에서 가짜 난쟁이 2명을 빼고 그 인덱스를 저장한뒤

다시 for문을 돌면서 저장된 인덱스를 제외하고 출력하였다. 

 

3) 코드

int main() {
	int arr[9];
	for (int i = 0; i < 9; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + 9); // permutation을 쓰기위한 오름차순
	
	do {
		int sum = 0;
		for (int i = 0; i < 7; i++) {
			
			sum = sum + arr[i];
		}
		if (sum == 100) {
			break;
		}
		
	} while (next_permutation(arr, arr + 9));// 크기만큼 인덱스를 계속 바꾼다 
	for (int i = 0; i < 7; i++) {
		cout << arr[i] << endl;
	}
}

 

int main() {
	int arr[9];
	for (int i = 0; i < 9; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + 9); // permutation을 쓰기위한 오름차순
	int sum = 0;
	for (int i = 0; i < 9; i++) {
		sum = sum + arr[i];
	}
	int ch1, ch2;
	bool flag = true;
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < i; j++) {
			if (sum - arr[i] - arr[j] == 100) {
				flag = false;
				ch1 = i;
				ch2 = j;
				break;
			}
		}
		if (flag == false) {
			break;
		}
	}
	for (int i = 0; i < 9; i++) {
		if (i == ch1 || i == ch2) {
			continue;
		}
		else {
			cout << arr[i] << endl;
		}
	}
}