[백준] 2798번: 블랙잭 C++로 풀어보기

2798번 설명

 

생각

맨 처음 든 생각:

 

벡터로 입력받아서 오름차순으로 정렬한 다음, M/3과 가장 가까운 수를 찾아서 그 수와 양 옆에 있는 수를 더한 값을 구하면 될 것 같다.

-> 정렬했을 때 붙어있는 세 값의 합만이 정답이 아니다. 반례가 있으므로 틀렸다.

 

두번째 든 생각:

 

벡터로 입력받아서 오름차순으로 정렬한 다음, (*it) + *(it+1) + *(it+2)가 m보다 클 때를 찾아서 그 때 *(it-1) + *it + *(it+1)을 구하면 될 것 같다.

-> 아까 위에 말했던 것처럼 정렬했을 때 붙어있는 세 값만이 정답이 아니다. 역시 틀렸다.

 

 

붙어있는 값들의 합만이 정답이 아니다. 그러면 어떻게 해야될까?

-> 삼중루프를 돌려서 m과 가장 가깝지만 m보다 작은 값을 찾는다.

여기서 주의해야 할 점은 삼중루프를 돌리다보니 vector의 iterator가 3개다. 그러므로 iterator가 같은 값들을 가리킬 때가 있는데 그 때는 빼주어야 한다. 아니면 같은 값을 여러번 더한 값으로 출력될 수도 있기 때문이다.

 

---

코드

#include <bits/stdc++.h>
using namespace std;


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	vector <int> v; // 숫자들을 정렬하기 위한 벡터
	vector <int> v2; // 숫자들을 비교하기 위한 벡터
	cin >> n >> m;


	while (n--) { // 숫자들을 입력받아서 벡터에 push한다.
		int x;
		cin >> x;
		v.push_back(x);
	}

	// v1 벡터를 내림차순으로 정렬(굳이 내림차순으로 안해도 된다.)
	sort(v.rbegin(), v.rend()); 
	

	for (auto it1 = v.begin(); it1 != v.end() - 2; it1++) {
		for (auto it2 = v.begin(); it2 != v.end() - 1; it2++) {
			for (auto it3 = v.begin(); it3 != v.end(); it3++) {
				// iterator들이 같지 않은 값들을 가리키고 세 수의 합이 m보다 작은 값들을 v2에 push한다.
				if (it1 != it2 && it1 != it3 && it2 != it3 && (*it1) + (*it2) + (*it3) <= m) {
					v2.push_back((*it1) + (*it2) + (*it3));
				}
			}
		}
	}
	// v2 벡터를 오름차순으로 정렬
	sort(v2.begin(), v2.end());

	// v2 벡터의 가장 오른쪽 값 출력
	cout << *(v2.end() - 1);


}

 

결과

2798번 결과

브론즈2라서 쉽게 풀릴 줄 알았는데 꽤 오래 걸렸다.

 

지금 solved.ac 클래스2 문제를 차례차례 풀어보고 있는 중이다. 7월 달 안까지는 다 끝내고 싶다.

 

배운 점:

벡터의 내림차순 정렬: sort(v.rbegin(), v.rend());