[class2] (백준 2798) 블랙잭

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

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

입력

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

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

출력

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

제한

예제 입력 1

5 21
5 6 7 8 9

예제 출력 1

21

예제 입력 2

10 500
93 181 245 214 315 36 185 138 216 295

예제 출력 2

497

힌트

W3sicHJvYmxlbV9pZCI6IjI3OTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlMTRcdWI3OTlcdWM3YWQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Y2U3NFx1YzljMFx1YjE3OFx1YzVkMFx1YzExYyBcdWM4MWNcdWM3N2MgXHVjNzc4XHVhZTMwIFx1Yzc4OFx1YjI5NCBcdWFjOGNcdWM3ODQgXHViZTE0XHViNzk5XHVjN2FkXHVjNzU4IFx1YWRkY1x1Y2U1OVx1Yzc0MCBcdWMwYzFcdWIyZjlcdWQ3ODggXHVjMjdkXHViMmU0LiBcdWNlNzRcdWI0ZGNcdWM3NTggXHVkNTY5XHVjNzc0IDIxXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTQgXHVkNTVjXHViM2M0IFx1YjBiNFx1YzVkMFx1YzExYywgXHVjZTc0XHViNGRjXHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHVkMDZjXHVhYzhjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NzRcdWIyZTQuIFx1YmUxNFx1Yjc5OVx1YzdhZFx1Yzc0MCBcdWNlNzRcdWM5YzBcdWIxNzhcdWI5YzhcdWIyZTQgXHViMmU0XHVjNTkxXHVkNTVjIFx1YWRkY1x1YzgxNVx1Yzc3NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1Y1x1YWQ2ZCBcdWNkNWNcdWFjZTBcdWM3NTggXHViZTE0XHViNzk5XHVjN2FkIFx1YWNlMFx1YzIxOCBcdWFlNDBcdWM4MTVcdWM3NzhcdWM3NDAgXHVjMGM4XHViODVjXHVjNmI0IFx1YmUxNFx1Yjc5OVx1YzdhZCBcdWFkZGNcdWNlNTlcdWM3NDQgXHViOWNjXHViNGU0XHVjNWI0IFx1YzBjMVx1YWRmYywgXHVjYzNkXHVjNjAxXHVjNzc0XHVjNjQwIFx1YWM4Y1x1Yzc4NFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWU0MFx1YzgxNVx1Yzc3OCBcdWJjODRcdWM4MDRcdWM3NTggXHViZTE0XHViNzk5XHVjN2FkXHVjNWQwXHVjMTFjIFx1YWMwMSBcdWNlNzRcdWI0ZGNcdWM1ZDBcdWIyOTQgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjLCBcdWI1MWNcdWI3ZWNcdWIyOTQgTlx1YzdhNVx1Yzc1OCBcdWNlNzRcdWI0ZGNcdWI5N2MgXHViYWE4XHViNDUwIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWJjZjRcdWM3NzRcdWIzYzRcdWI4NWQgXHViYzE0XHViMmU1XHVjNWQwIFx1YjE5M1x1YjI5NFx1YjJlNC4gXHVhZGY4XHViN2YwIFx1ZDZjNFx1YzVkMCBcdWI1MWNcdWI3ZWNcdWIyOTQgXHVjMjJiXHVjNzkwIE1cdWM3NDQgXHVkMDZjXHVhYzhjIFx1YzY3OFx1Y2U1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjODFjIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YjI5NCBcdWM4MWNcdWQ1NWNcdWI0MWMgXHVjMmRjXHVhYzA0IFx1YzU0OFx1YzVkMCBOXHVjN2E1XHVjNzU4IFx1Y2U3NFx1YjRkYyBcdWM5MTFcdWM1ZDBcdWMxMWMgM1x1YzdhNVx1Yzc1OCBcdWNlNzRcdWI0ZGNcdWI5N2MgXHVhY2U4XHViNzdjXHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViZTE0XHViNzk5XHVjN2FkIFx1YmNjMFx1ZDYxNSBcdWFjOGNcdWM3ODRcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHVhY2UwXHViOTc4IFx1Y2U3NFx1YjRkY1x1Yzc1OCBcdWQ1NjlcdWM3NDAgTVx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0XHVjMTFjIE1cdWFjZmMmbmJzcDtcdWNkNWNcdWIzMDBcdWQ1NWMgXHVhYzAwXHVhZTVkXHVhYzhjIFx1YjljY1x1YjRlNFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5cdWM3YTVcdWM3NTggXHVjZTc0XHViNGRjXHVjNWQwIFx1YzM2OFx1YzgzOCBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIE1cdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NFx1YzExYyBNXHVjNWQwIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWFjMDBcdWFlNGNcdWM2YjQgXHVjZTc0XHViNGRjIDNcdWM3YTVcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YWQ2Y1x1ZDU3NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2U3NFx1YjRkY1x1Yzc1OCBcdWFjMWNcdWMyMTggTigzICZsZTsmbmJzcDtOICZsZTsmbmJzcDsxMDApXHVhY2ZjIE0oMTAgJmxlOyZuYnNwO00gJmxlOyZuYnNwOzMwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNlNzRcdWI0ZGNcdWM1ZDAgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWM3NzQgXHVhYzEyXHVjNzQwIDEwMCwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NjlcdWM3NzQgTVx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0IFx1Y2U3NFx1YjRkYyAzXHVjN2E1XHVjNzQ0IFx1Y2MzZVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjljYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTVx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0XHVjMTFjIE1cdWM1ZDAgXHVjZDVjXHViMzAwXHVkNTVjIFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWNlNzRcdWI0ZGMgM1x1YzdhNVx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI3OTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJKQUNLIiwiZGVzY3JpcHRpb24iOiI8cD5JbiAmbGRxdW87QmxhY2tqYWNrJnJkcXVvOywgYSBwb3B1bGFyIGNhcmQgZ2FtZSwgdGhlIGdvYWwgaXMgdG8gaGF2ZSBjYXJkcyB3aGljaCBzdW0gdXAgdG8gbGFyZ2VzdCBudW1iZXIgbm90IGV4Y2VlZGluZyAyMS4gTWlya28gY2FtZSB1cCB3aXRoIGhpcyBvd24gdmVyc2lvbiBvZiB0aGlzIGdhbWUuPFwvcD5cclxuXHJcbjxwPkluIE1pcmtvXHUyMDFmcyBnYW1lLCBjYXJkcyBoYXZlIHBvc2l0aXZlIGludGVnZXJzIHdyaXR0ZW4gb24gdGhlbS4gVGhlIHBsYXllciBpcyBnaXZlbiBhIHNldCBvZiBjYXJkcyBhbmQgYW4gaW50ZWdlciBNLiBIZSBtdXN0IGNob29zZSB0aHJlZSBjYXJkcyBmcm9tIHRoaXMgc2V0IHNvIHRoYXQgdGhlaXIgc3VtIGNvbWVzIGFzIGNsb3NlIGFzIHBvc3NpYmxlIHRvIE0gd2l0aG91dCBleGNlZWRpbmcgaXQuIFRoaXMgaXMgbm90IGFsd2F5cyBlYXN5IHNpbmNlIHRoZXJlIGNhbiBiZSBhIGh1bmRyZWQgb2YgY2FyZHMgaW4gdGhlIGdpdmVuIHNldC48XC9wPlxyXG5cclxuPHA+SGVscCBNaXJrbyBieSB3cml0aW5nIGEgcHJvZ3JhbSB0aGF0IGZpbmRzIHRoZSBiZXN0IHBvc3NpYmxlIG91dGNvbWUgb2YgZ2l2ZW4gZ2FtZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIGludGVnZXIgTiAoMyAmbGU7IE4gJmxlOyAxMDApLCB0aGUgbnVtYmVyIG9mIGNhcmRzLCBhbmQgTSAoMTAgJmxlOyBNICZsZTsgMzAwIDAwMCksIHRoZSBudW1iZXIgdGhhdCB3ZSBtdXN0IG5vdCBleGNlZWQuPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgbGluZSBjb250YWlucyBudW1iZXJzIHdyaXR0ZW4gb24gTWlya29cdTIwMWZzIGNhcmRzOiBOIGRpc3RpbmN0IHNwYWNlLXNlcGFyYXRlZCBwb3NpdGl2ZSBpbnRlZ2VycyBsZXNzIHRoYW4gMTAwIDAwMC48XC9wPlxyXG5cclxuPHA+VGhlcmUgd2lsbCBhbHdheXMgZXhpc3Qgc29tZSB0aHJlZSBjYXJkcyB3aG9zZSBzdW0gaXMgbm90IGdyZWF0ZXIgdGhhbiBNLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgbGFyZ2VzdCBwb3NzaWJsZSBzdW0gd2UgY2FuIG9idGFpbi48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #6 1번

• 문제를 번역한 사람: baekjoon
• 빠진 조건을 찾은 사람: bupjae
• 문제의 오타를 찾은 사람: eric00513, joonas, otter66

#include <iostream>

using namespace std;

int main()
{
    int card[100];
    int goal, cardN;
    int result=0;
    int sum;
    
    cin >> cardN >> goal;
    
    for(int i = 0; i < cardN; i++)
    {
        cin >> card[i];
    }
    
    for(int i =0 ; i < cardN-2 ; i++)
    {
        for(int j=i+1;j<cardN-1;j++)
        {
            for(int k = j+1; k< cardN;k++)
            {
                sum = card[i]+card[j]+card[k];
                if(sum <= goal && sum > result)
                    result = sum;
            }
        }
    }
    
    cout << result << endl;
    return 0;
}