오늘의 문제는 “2798번 블랙잭”.
기존 블랙잭이 21을 만드는 게임이라면, 이 문제에서는 n개의 양의 정수 중에서 3개를 골라 그 합이 정수 m을 넘지 않으면서 m에 가깝게 만들어야 한다.
처음에는 n개의 정수를 정렬한 후, 전체 탐색을 하려고 했다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
int main()
{
int n, m, x, sum;
int min = 100000000;
vector <int> arr;
cin >> n >> m;
for (int i = 0; i < n; i++) //입력
{
cin >> x;
arr.push_back(x);
}
sort(arr.begin(), arr.end()); //정렬
for (int i = 0; i < arr.size() - 2; i++) //수 3개를 고르는 모든 경우의 수
{
for (int j = i + 1; j < arr.size() - 1; j++)
{
for (int k = j + 1; k < arr.size(); k++)
{
sum = arr[i] + arr[j] + arr[k]; //합해서
x = abs(m - sum);
if (x == 0) // m == sum 이면 min = 0이고 break
{
min = 0;
i = arr.size();
j = arr.size();
k = arr.size();
}
else if(x < min) //아닌 경우 min = x로 min 초기화
{
min = x;
}
}
}
}
cout << m - x << endl;
return 0;
}두 군데에서 틀렸는데, 우선 최종 결과값을 m - x가 아니라 m - min을 출력해야 한다.
그리고 x가 m과 세 수의 합의 차이의 절댓값이기 때문에 세 수의 합이 m보다 큰 경우를 걸러내지 못한다.
이 두 가지를 수정하면
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
int main()
{
int n, m, x, sum;
int min = 100000000;
vector <int> arr;
cin >> n >> m;
for (int i = 0; i < n; i++) //입력
{
cin >> x;
arr.push_back(x);
}
sort(arr.begin(), arr.end()); //정렬
for (int i = 0; i < arr.size() - 2; i++) //수 3개를 고르는 모든 경우의 수
{
for (int j = i + 1; j < arr.size() - 1; j++)
{
for (int k = j + 1; k < arr.size(); k++)
{
sum = arr[i] + arr[j] + arr[k];
x = m - sum;
if (x == 0) //m == sum 이면 min = 0이고 break
{
min = 0;
i = arr.size();
j = arr.size();
k = arr.size();
}
else if(0 < x && x < min) //세 수의 합이 m을 넘지 않으면서 m에 더 가까우면 min값 최신화
{
min = x;
}
}
}
}
cout << m - min << endl;
return 0;
}문제를 풀면서 굳이 정렬이 필요한지 궁금했다.
그래서 입력 받는 부분을 좀 고쳤다.
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int main()
{
int n, m, x;
int min = 100000000;
vector <int> arr;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> x;
if (x <= m) //입력받은 정수가 m보다 작은 경우에 한하여 arr에 push
{
arr.push_back(x);
}
}
for (int i = 0; i < arr.size() - 2; i++) //수 3개를 고르는 모든 경우의 수
{
for (int j = i + 1; j < arr.size() - 1; j++)
{
for (int k = j + 1; k < arr.size(); k++)
{
x = m - arr[i] - arr[j] - arr[k];
if (x == 0) //m == sum 이면 min = 0이고 break
{
min = 0;
i = arr.size();
j = arr.size();
k = arr.size();
}
else if(0 < x && x < min) //세 수의 합이 m을 넘지 않으면서 m에 더 가까우면 min값 최신화
{
min = x;
}
}
}
}
cout << m - min << endl;
return 0;
}굳이 정렬하지 않아도 정답이 잘 나온다.