알고리즘 ] 4. 완전탐색

완전탐색

- 완전 탐색은 기본적인 알고리즘으로 전체를 다 돌면서 일일이 확인하는 알고리즘이다.

- 적은 량의 데이터를 순회할 때에만 사용 가능하다.

 

1. 난쟁이 문제

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

- 9명의 난쟁이중 7명을 고르는 문제

- 7명의 난쟁이 키의 합이 100

 

1) 해결방법

- 전체를 돌면서 모든 경우의 수를 계산하는 것이 아닌 2명을 제외하는 형태로 진행해야 한다.

- 2명을 제외하기 때문에 2중 for문을 돌면서 제외해하면서 계산한다.

 

// ConsoleApplication1.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <algorithm>

using namespace std;

#define SMALL 9
int main()
{
	int small[SMALL];
	
	for (int smallCnt = 0; smallCnt < SMALL; smallCnt++)
	{
		cin >> small[smallCnt];
	}	
	sort(small, small + SMALL);

	int totalSum = 0;
	for (int entireIdx = 0; entireIdx < SMALL; entireIdx++)
	{
		totalSum += small[entireIdx];
	}


	for (int cnt1 = 0; cnt1 < SMALL; cnt1++)
	{
		for (int cnt2 = 0; cnt2 < SMALL; cnt2++)
		{
			if (cnt1 != cnt2)
			{
				if (totalSum - small[cnt1] - small[cnt2] == 100)
				{
					for (int printIdx = 0; printIdx < SMALL; printIdx++)
					{
						if (printIdx != cnt1 && printIdx != cnt2)
						{
							cout << small[printIdx] << endl;
						}
					}

					return 0;
				}
			}
		}
	}
}