[C++] 백준 2798번 - 기본 풀이와 분할정복 시도 2가지 풀이

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

풀이1

#include <iostream>

int main() {
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  
  int N, M; cin >> N >> M;
  int *arr = new int[N];
  int sum = 0, tmp;

  for (int i = 0; i < N; i++) {
    cin >> arr[i];
    for (int j = 0; j < i; j++) {
      for (int k = 1; k < i; k++) {
        tmp = arr[i] + arr[j] + arr[k];
        if (j == k) continue;
        if (M < tmp) continue;
        if (M - tmp < M - sum) sum = tmp;
      }
    }
  }
  cout << sum << "\n";
  delete[] arr;
  return 0;
}

해설

1행과 2행은 기존의 C언어에서 사용하던 scanf / printf / puts / getchar / putchar와 같은 함수를 사용하지 않도록 만듦으로써 프로그램의 속도를 조금 더 빠르게 할 수 있어요. 백준 15552번을 참고해주세요!

 

N과 M을 입력받은 후 N개 숫자를 입력받는 동시에 지금까지 입력받은 수끼리 비교하는 방법을 사용했어요.

 

두 개의 for문 j와 k가 같은 숫자를 가리키지 않도록 조건 처리를 해주고, 또 i, j, k끼리 더한 값이 M보다 큰 경우를 제외하도록 만들었어요.

 

그 모든 조건을 이겨내고 M와 더 가까운 숫자를 sum에 저장하기를 반복하면서 정답을 알아내요!

풀이2

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

using namespace std;

int main() {
  cin.tie(NULL);
  ios::sync_with_stdio(false);

  int N, M;
  cin >> N >> M;

  vector<int> cards(N);
  for (int i = 0; i < N; i++) {
    cin >> cards[i];
  }

  int groupSize = 5;
  int groupCount = (N + groupSize - 1) / groupSize;
  vector<int> locMin(groupCount);

  for (int i = 0; i < N; i++) {
    int groupIndex = i / groupSize;
    locMin[groupIndex] = min(locMin[groupIndex], cards[i]);
  }

  int max_sum = 0;

  for (int i = 0; i < N - 1; i++) {
    for (int j = i + 1; j < N; j++) {
      int partialSum = cards[i] + cards[j];
      if (partialSum >= M) continue;
      
      for (int k = 0; k < groupCount; k++) {
        for (int l = k * groupSize; l < (k + 1) * groupSize && l < N; l++) {
          if (l != i && l != j) {
            int totalSum = partialSum + cards[l];
            if (totalSum <= M) {
              max_sum = max(max_sum, totalSum);
            }
          }
        }
      }
    }
  }
  cout << max_sum << '\n';
  return 0;
}

해설

divide and conquer(분할정복) 방법을 사용해보면 어떨까는 생각이 들었어요.

 

먼저 쭉 입력받고서 그 숫자를 5개씩 묶은 다음에, 묶음마다 최솟값을 따로 리스트에 저장해두어요.

 

그런 다음 두 개의 숫자를 꺼낸 후 그 합을 최솟값 리스트 아이템과 비교하면서 만일 최솟값과 더했을 때 M을 넘어가면 그 묶음에 있는 숫자들은 모두 M을 넘길테니 묶음채로 넘어가는 방법을 생각했어요!

 

그런데 실제 반복되는 횟수는 적더라도 for문이 4번 중첩되어 있고 코드가 길어져서 선호하는 전략은 아닌 것 같아요 ; ;

 

혹시 더 나은 방법이 있다면 소개해주세요!