BOJ 2309 일곱난쟁이

문제출처 : https://www.acmicpc.net/problem/2309

1. 문제요약

- 9명의 난쟁이 중 키의 합이 100이 되는 7명의 난쟁이를 뽑아 오름차순으로 출력

2. 접근방법

- 단순하게 9명 중 7명을 뽑아서 키의 합이 100이 되면 출력 후 종료 => 조합 9C7

- 9C7 = 9C2 이므로 9명의 총 합에서 100을 제외한 값을 만족하는 2명만 뽑아서 나머지를 출력

3. 시간복잡도

- 9C7 재귀 구현의 경우 O(2^N) = 2^9

- 9C2 for 구현의 경우 O(NC2) = 9C2 => for를 계산해보면 8 + 7 + 6 + 5 + ... + 2 + 1 = 36

4. 회고

- 9C7을 재귀로 구현했을 때

  재귀에서 '정답인 경우'와 '정답이 아닌 경우'를 잘못 선정해서 무한루프에...

  base case를 잘 생각해보자

- 조합을 재귀 말고 쉽게 구현할 수 있는 방법이 있을까? 아직 지하 밑바닥에 있어서 좀 더 경험이 필요할 듯

- 9C2를 for로 구현했을 때 sort에서 a+10을 해버렸....왜 0이 나오나 했네

소스코드 : 9C2

#include<iostream>
#include<algorithm>
using namespace std;

int a[9];

int main(void){
	int sum = 0;
	for (int i = 0; i < 9; i++){
		cin >> a[i];
		sum += a[i];
	}

	for (int i = 0; i < 8; i++){
		for (int j = i + 1; j < 9; j++){
			if (a[i] + a[j] == sum - 100){
				a[i] = 1000;
				a[j] = 1000;
			}
		}
	}

	sort(a, a + 9);
	for (int i = 0; i < 7; i++)
		cout << a[i] << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]