본문 바로가기
Problem Solving/백준

[백준] 2309번 : 일곱 난쟁이

by shinbian11 2020. 7. 11.

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

 

2309번: 일곱 난쟁이

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

www.acmicpc.net


<C++>

#include <bits/stdc++.h>
using namespace std;
int shortman[10];
int main()
{
	int sum = 0;
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	for (int i = 0; i < 9; i++)
	{
		cin >> shortman[i];
		sum += shortman[i];
	}
	sort(shortman, shortman + 9);
	for (int i = 0; i < 9; i++)
	{
		for (int j = i + 1; j < 9; j++)
		{
			if (sum - shortman[i] - shortman[j] == 100)
			{
				for (int k = 0; k < 9; k++)
				{
					if ((i == k) || (j == k))
						continue;
					cout << shortman[k] << endl;
				}
                		return 0;
			}
		}
	}
}

 

> 모든 경우의 수를 다 따져도 몇가지 안되기 때문에, 브루트 포스를 사용하자.

> 일일히 7명의 난쟁이를 찾으려고 애쓰지 말고, 그냥 밑의 방법을 이용하자.

> 9명 전체 난쟁이들의 키의 합(sum)에서 두 명의 난쟁이 키를 뺐을 때 100이 나온다면 그 두명의 난쟁이를 제외하고

나머지 난쟁이들의 키를 모두 출력하면 된다.

> 답이 되는 경우를 딱 한가지만 출력하면 되므로, 출력이 다 끝난 후에는 return 0; 으로 정상적으로 종료하고 나온다.