백준 2309번 일곱 난쟁이(C++)

정답 코드

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

vector <int> arr1(9,0);
vector <int> arr2(9,0);

void	result(int a1,int a2)
{
	for (int i=0; i<9; i++)
	{
		if (i != a1 && i != a2)
			cout << arr1[i] << '\n';
	}

}

int main()
{
	ios:: sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	for (int i=0; i < 9; i++)
	{
		cin >> arr1[i];
		if (i != 0)
			arr2[i] = arr1[i] + arr2[i-1];
		else
			arr2[i] = arr1[i];
	}
	sort(arr1.begin(), arr1.end());
	for (int i =0 ; i < 9; i++)
	{
		for (int j = i+1; j < 9; j++)
		{
			if (arr2[8] - (arr1[i] + arr1[j]) == 100)
			{
				result(i,j);
				return (0);
			}
		}
	}
	return (0);
}

문제 풀이의 흐름

난쟁이가 총 9명이 들어왔고 7명으로 줄여야 하기 때문에 9명중에 7명을 선택해서 100을 찾는 것 보다는 9명의 합에서 2명의 조합을 빼는게 낫다고 생각했다.

1. 9명의 키를 입력 받는다.

2. 입력 받으면서 전체의 합을 구해준다.

3. 정렬을 해주고

4. 100이 되는 경우에 함수로 가서 그 경우를 출력을 해주고 종료한다!

주의 할 점

이 문제는 딱히 어려운 점은 없었지만, 한번 오답을 했는데 그 이유는 정답이 2개이상인 경우에 모든 경우를 다 출력해서 틀렸었다. 즉 저기 return문을 안 넣어줘서 틀린 것이다.

정답을 한번 출력하고 return 을 넣어준 순간 바로 통과를 했다.

반성 및 고찰

너무 누적합이라는 풀이에 눈이 맞춰져 있었다. 그래서 굳이 배열을 9로 선언해서 누적합을 구할 필요는 없었지만 누적합 강의를 막 본 상태라서 통과를 다음과 같이 했다. 그냥 sum변수 하나로 충분했다. 그리고 set을 써서 풀었다면 아마 정렬도 하지 않아도 돼서 더 간단한 문제가 됐을 수도 있을 것 같다. 다음번에는 set도 사용해봐야겠다.

또한 next_permutation이라는 함수를 사용해서 푼 답도 있던데 기회가 된다면 순열 함수도 사용을 해보겠다.

Uploaded by N2T