[C++] 백준 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장의 합을 출력한다.

접근

이 문제를 풀기전에 문제가 브루트포스 알고리즘과 관련된 문제였어서 이 알고리즘과 관련된 문제를 풀어 보고싶어서 풀었다

모든 경우의 수를 대입하면서 조건에 만족하는 답을 찾으면 된다

그래서 전체카드에서 3개를 고를수 있는 모든 경우의 수를 구해야해서 3중 for문을 썼다

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#include <cmath>
using namespace std;


int main() {

    int n, m;
    scanf("%d %d", &n, &m);

    vector<int> num(n);
    int result = 0;

    for (int i = 0; i < n; i++) {
        scanf("%d", &num[i]);//각 카드의 숫자를 벡터에 입력받음 
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n ; j++) {
            for(int k = j+1; k < n ; k++) {
                if (num[i] + num[j] + num[k] <= m) {
                    result = max(result, num[i] + num[j] + num[k]);
                }
            }
        }
    }
    printf("%d", result);
    
    return 0;
}

리뷰

삼중 for문으로 카드3개를 뽑는 모든 경우의 수를 구했다

근데 여기서 내가 실수한게 있는데 나는 처음에 이렇게 for문을 적었다

for (int i = 0; i < n; i++) {
        for (int j = 1; j < n ; j++) {
            for(int k = 2; k < n ; k++) {

내가 적은 코드의문제점은

j와 k의값이 각각 1과 2로 설정되어있는게 문제이다 이 경우에 중복된 경우가 나올수있는게 문제점이다

그래서 중복된 값을 안나오게 하기 위해 j=i+1 k=j+1이라고 해준다

이부분만 빼면 뭐 어렵지 않게 풀었다

근데 아직까지 100프로 이해는 못했따... 내가 박댁알인가 

출처 

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