[C++/BOJ] 백준 2798 블랙잭(완전탐색)

https://github.com/tony9402/baekjoon/tree/main/brute_force

GitHub - tony9402/baekjoon: 코딩테스트 대비 문제집(Baekjoon Online Judge)

여기에 있는 완탐 추천 문제들을 겨울방학동안 모두 풀려고 한다.

첫번째 문제인 피로도는 쉽게 풀었다. 

 

 

두번째 문제인 블랙잭...쉬운것같은데 바로 풀리지는 않는다. 

 

 

 

 

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

2798번: 블랙잭

 

 

 

주어진 n개의 숫자들중 3개씩 더한 합이 가장 m과 근접한 것을 찾는 문제다.

3개씩 더한 합을 구하는게 문제다.

 

 

3중 for문이 생각이 났다.

n은 100까지 이고 for문을 돌리면 100^3이므로 1000000이다. 백만이므로 1초가 안걸린다.

시간제한은 걸리지 않을 것이다.

 

<3중 for문에서 겹치지않게 3개의 숫자를 뽑아 더한것이 m과 가장 가까운 값을 MAX에 저장하였다>

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector <int> v;
int n, m;
int sum, tmp, MAX;
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	v.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		v[i]=tmp;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				if (i == j || j == k || k == i) continue;
				sum = v[i] + v[j] + v[k];
				if (sum > m) continue;
				if (m - MAX > m - sum) MAX = sum;
			}
		}
	}
	cout << MAX;
}

 

-> 계속 잘못된 출력이 나와서 3중 for문에 문제가 있나 했는데 

벡터 부분에서 문제가 발생한것이었다.

 

v.push_back(tmp)를 하면 벡터에 0부터 n까지 차곡차곡 쌓일거라 생각했는데 그게 아니라

n이후로 차곡차곡 쌓이더라

 

 

vector를 resize(n)를 하면 사이즈만 정해주는 줄 알았는데 (n)까지의 모든 벡터를 0으로 초기화해준다. 

 

 

오늘 또 하나 배웠다! 하하 

 

 

 

브론즈까지는 해설을 보지않고도 풀수있는 실력이 됐나보다 

다행이다. 앞으로도 꾸준히 해보자