백준 2798번 - 블랙잭(순열?, brute-force)

문제

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

C++ 풀이

다행히 N이 100까지면 조합의 경우의 수를 따지더라도 최대 10^6(백만) 보다 작을 것이므로 무지성 brute-force를 통해 풀이 할 수 있지 않을까? 해서 삼중 for문으로 구현한 풀이

#include <iostream>

using namespace std;

int main()
{
    int N,M,a,i=0;
    cin >> N >> M;
    
    int d[N+1], close=M,ans;
    while(cin>>a)
        d[i++]=a;
    for(i=0;i<N; i++) {
        for(int j=i+1;j<N;j++) {
            for(int k=j+1;k<N;k++) {
                if ( (M >= d[i]+d[j]+d[k]) && (M - (d[i]+d[j]+d[k]) < close )) {
                    close = M-(d[i]+d[j]+d[k]);
                    ans = d[i]+d[j]+d[k];
                }
            }
        }
    }
    cout<<ans;
}