[C++] BOJ (백준) 2798 : 블랙잭

문제

2798번: 블랙잭 (acmicpc.net)

2798번: 블랙잭

코드 1

#include <iostream>
#include <vector>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;
  vector<int> v(n);
  for (int &i: v) {
    cin >> i;
  }

  int mx = -1;
  for (int i = 0; i < n - 2; i++) {
    for (int j = i + 1; j < n - 1; j++) {
      for (int k = j + 1; k < n; k++) {
        int sum = v[i] + v[j] + v[k];
        if (sum <= m && sum > mx) mx = sum;
      }
    }
  }
  cout << mx;
  return 0;
}

 

설명

그냥 3중 for문을 돌리면 된다...
시간복잡도는 O(n^3)으로 매우 느리지만, n의 최댓값이 100에 불과하기 때문에 가능하다.

 

코드 2

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
vector<int> v;

// value 이하인 최댓값을 찾는다.
int binarySearch(int low, int high, int value) {
  if (v[high] <= value) return v[high];
  int res = -1;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (v[mid] == value) return value;
    if (v[mid] < value) {
      res = v[mid];
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m;
  v = vector<int>(n);
  for (int &i: v) {
    cin >> i;
  }
  sort(v.begin(), v.end());

  int mx = -1;
  for (int i = 0; i < n - 2; i++) {
    for (int j = i + 1; j < n - 1; j++) {
      int sum = v[i] + v[j];
      if (sum >= m) continue;
      sum += binarySearch(j + 1, n - 1, m - sum);
      if (sum > mx) mx = sum;
    }
  }
  cout << mx;
  return 0;
}

설명

위의 코드에서 i, j를 구하는 과정은 그대로 두고 k를 이분탐색으로 구할 수 있다.
시간복잡도는 O(N^2log n)이 된다.