[백준2309] - 일곱난쟁이(C++)

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

2309번: 일곱 난쟁이

아이디어

 

아홉 난쟁이의 키를 모두 벡터에 넣은 뒤 합(sum)을 구한다. 그리고 sum과 100의 차를 구해 n1이라 하자. 그런 뒤 이중 포문을 이용해 벡터의 값 중 2개를 골라 더한 값이 n1일때 이중포문을 탈출한다. 그리고 벡터에서 해당 원소들을 지워준 뒤 정렬하여 출력한다.

 

조금 더 자세히 설명하자면 아래의 그림과 같다.

i=0~7, j=i+1~8을 반복하는 이중 포문을 만들어 위와 같이 하나씩 더해가며 n1과 값을 비교한다. i는 진한 파랑, j는 파란색 부분이다.

 

작성한 코드

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

int main() {
	int a, b, c, d, e,f,g,h,i;
	cin >> a >> b >> c >> d >> e>>f>>g>>h>>i;
	vector<int> v2{ a, b, c, d, e,f,g,h,i};
	int sum,n1;
	sum = accumulate(v2.begin(), v2.end(), 0);
	n1 = sum - 100;

	for (int i = 0; i < 8; i++) {
		for (int j = i + 1; j < 9; j++) {
			if (v2[i] + v2[j] == n1) {
				v2.erase(v2.begin() + i); //인덱스 번호가 i인 요소를 지운다.
				v2.erase(v2.begin() + j-1); //i는 무조건 j보다 작으므로 j-1번째 요소를 지워야 한다.
				i = 8;//이중 for문 탈출     //인덱스 번호가 i인 요소를 지우고 나면 벡터의 크기도 1이 줄어든다.
				break;//이중 for문 탈출     //즉 j번째 원소를 지우면 찾은 값 뒤의 원소를 지우게 된다.
			}
		}
	}
	
	sort(v2.begin(), v2.end()); //일곱 난쟁이의 키가 들어있는 벡터를 정렬
	for (int i = 0; i < 7; i++) {  //하나씩 출력
		cout << v2[i] << '\n';
	}

}

 

이론 정리

 

브루트 포스(brute force)

brute : 무식한   force : 힘

-> 가능한 모든 경우에 대해 직접 해보는 방법

 

#include <algorithm>

-> sort함수 사용 위함

vector<int> v{ 2, 1, 3 ,0 };
sort(v.begin(), v.end());
// v{0, 1, 2, 3}

 

#include <numeric>

->accumulate함수 사용 위함

vector<int> v{1, 3, 9, 2}
sum = accumulate(v2.begin(), v2.end(), 0); //accumulate(범위 시작, 범위 끝, 합의 초기값)
//sum = 15