언제품?

: 220915 01:00 ~ 01:19

최근 풀이

-> 순서와 상관없이 9명 중에서 7명을 뽑는 것이므로,
조합을 생각해야 함.

• 코드

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

int main()
{
	vector<int>v(9);

	for (int i = 0; i < 9; ++i)
	{
		cin >> v[i];
	}

	sort(v.begin(), v.end());

	do 
	{
		int sum = 0;
		for (int i = 0; i < 7; ++i)
		{
			sum += v[i];
		}
		if (sum == 100)
		{
			for (int i = 0; i < 7; ++i)
			{
				cout << v[i] << endl;
			}
			return 0;
		}

	} while (next_permutation(v.begin(), v.end()));

}

잘못된 풀이

• for문 7번 돌렸다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main() {
	
	vector<int>result(7, 0);

	int m = 9;
	vector<int>v(m, 0);

	for (int i = 0; i < m; i++)
		cin >> v[i];

	int sum = 0; 
	sort(v.begin(), v.end());

	for (int a = 0; a < m; a++)
	{
		for (int b = a + 1; b < m; b++)
		{
			for (int c = b + 1; c < m; c++)
			{
				for (int d = c + 1; d < m; d++)
				{
					for (int e = d + 1; e < m; e++)
					{
						for (int f = e + 1; f < m; f++)
						{
							for (int g = f + 1; g < m; g++)
							{
								sum = v[a] + v[b] + v[c]
									+ v[d] + v[e] + v[f] + v[g];

								if (sum <= 100)
								{
									result[0] = v[a];
									result[1] = v[b];
									result[2] = v[c];
									result[3] = v[d];
									result[4] = v[e];
									result[5] = v[f];
									result[6] = v[g];
									//cout << v[a] << endl;
									//cout << v[b] << endl;
									//cout << v[c] << endl;
									//cout << v[d] << endl;
									//cout << v[e] << endl;
									//cout << v[f] << endl;
									//cout << v[g] << endl;
								}
							}
						}
					}
				}
			}
		}
	}

	for (int i = 0; i < result.size(); i++)
	{
		cout << result[i] << endl;
	}
	return 0;
}

풀이 전략

• 9명 중에서 7명을 고르는 것은 7명 중에서 2명을 고르는 것과 동일하다.

• 9명을 모두 더한 뒤에 2명을 빼는 방법으로 구현하면
  n제곱으로 구할수 있다. 하지만 여기서 뺀 인덱스를 알아야 하므로,
  뺀값을 탐색하는 반복문을 추가해 n세제곱으로 구현할 수 있다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main() {	
	
	int m = 9;
	vector<int>v(m, 0);
	int sum = 0;
	for (int i = 0; i < m; i++)
	{
		cin >> v[i];
		sum += v[i];
	}

	
	sort(v.begin(), v.end());

	for (int i = 0; i < 9; i++)
	{
		for (int j = i + 1; j < 9; j++)
		{
			if (sum - v[i] - v[j] == 100)
			{
				//출력하기 위해서는 한번 더 for문을 돌리면서 인덱스 안뺀 것들을 출력하면된다.
				for (int k = 0; k < 9; k++)
				{
					if (k == i || k == j)
						continue;
					cout << v[k] << endl;
				}
				return;
			}
		}
	}



	return 0;
}