문제 2798 ( C++ )

brute force method 으로 해결하는 문제

 

 

코드

#include <iostream>
#include <set>
 
using namespace std;
 
int main(void) {
 
  set<int> s;
 
  int N , M;
 
  cin >> N >> M;
 
  int * arr = (int*)malloc( sizeof(int) * N );
 
  for (int i = 0; i < N ; i++ ) {
    cin >> arr[i];
  }
 
  for (int i = 0; i < N-2 ; i++ ) {
    for (int j = i + 1 ; j < N - 1 ; j++ ) {
      for ( int z = j + 1 ; z < N ; z++ ) {
        int sum = arr[i] + arr[j] + arr[z];
        s.insert(sum);
      }
    }
  }
 
  set<int>::iterator iter;
 
  int best = M;
 
  while ( 1 ) {
    iter = s.find(best);
    if ( iter != s.end() ) break;
 
    best--;
  }
 
  cout << *iter;
 
 
  free(arr);
  arr = NULL;
}
 

 

코드 설명

정수형 집합 s 와 길이 N 인 정수형 배열을 동적할당으로 생성한다

 

brute force method 으로 N 개의 정수가 주어졌을때 서로 다른 3장을 뽑아 만들 수 있는 합의 경우를 집합 s 에 삽입한다.

 

M에 최대한 가까운 3장의 합을 출력하면 되므로 중복된 값은 필요하지 않으므로 집합에 삽입한것

 

지시자(iterator)를 이용하여 M에 최대한 가까운 합을 찾는다

 

답을 출력

 

 

결과