[C++] BOJ 2798 JACK 블랙잭

문제

백준 2798번

www.acmicpc.net/problem/2798

2798번: 블랙잭

코드

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

int n, m, arr[100], res;
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)cin >> arr[i];
	
	for (int i = n-1; i >= 0; i--) {
		for (int j = i - 1; j >= 0; j--) {
			for (int k = j - 1; k >= 0; k--) {
				if (arr[i] + arr[j] + arr[k] <= m) {
					res = max(res, arr[i] + arr[j] + arr[k]);
				}
			}
		}
	}
	cout << res;
}

풀이방법

모든 3개 숫자의 경우마다 합을 구해서, 이 값이 m보다 작거나 같으면 res에 최댓값을 갱신하며 저장한다. 모든 과정이 끝난 후 res값을 출력한다.

고민과정

처음에 다른 방식으로 풀었다가 시간이랑 공간 효율성이 너무 떨어지길래 코드를 고쳤다. 처음 코드는 다음과 같았다.

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

int n, m, arr[100];
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)cin >> arr[i];
	vector<int> sum;

	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			for (int k = j + 1; k < n; k++) {
				sum.push_back(arr[i]+arr[j]+arr[k]);
			}
		}
	}

	sort(sum.begin(), sum.end());
	for (int i = sum.size() - 1; i >= 0; i--) {
		if (sum[i] <= m) {
			cout << sum[i];
			break;
		}
	}
}