백준 2798 블랙잭

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

Problem

앞면에 양의 정수가 적힌 카드 N 장이 주어진다.
이들 중 3 장을 뽑아서, 각 카드에 적힌 숫자의 합산이 목표 숫자 M 을 넘지 않는 한에서 최대한 가까운 값으로 만들어야 한다.

Input

• 카드의 개수 N(3 ≤ N ≤ 100)
• 목표 숫자 M(10 ≤ M ≤ 300,000)
• 각 카드에 적힌 숫자 x(0 < x < 100,000)
• 해가 존재하는 경우의 입력만 주어짐

Output

• 뽑힌 세 카드의 합

Plan 1

Method
무식하게 풀기
1. 카드 오름차순 정렬
2. max_sum = 0 으로 초기화
2. 탐색 시작, 앞에서부터 하나하나 더해서 합산 값 sum 만들기
3. max_sum < sum <= M 이면 max_sum = sum
4. 합산 값이 M 을 넘으면 탐색 종료하고 직전 값 사용
Review

1 4 8 10 1000

의 경우, (1, 10, 1000)에서 종료하게 되면 (4, 8, 10) 탐색 불가!
종료 조건 재 검토해야 함

Plan 2

Method
Plan 1과 같지만, 종료 조건은 연속하는 3개의 수의 합이 M을 넘게 되면 탐색 종료
Review
해당 알고리즘의 속도는 종료 조건을 찾는 위치에 달려있음

Code

#include <iostream>
#include <cstdbool>
#include <algorithm>

using namespace std;

#define CARD_MAX_NUM 100

static int num_cards;
static int cards[CARD_MAX_NUM];

static int target_num = 0;

static bool is_exit_condition(int index)
{
    int sum = 0;
    
    int end = index + 3;
    if (end > num_cards) {
        end = num_cards;
    }
    
    for (int i = index; i < end; i++) {
        sum += cards[i];
    }
    
    return (sum > target_num) ? true : false;
}

static int search(void)
{
    sort(cards, cards + num_cards);

    int max_sum = 0;
    for (int i = 0; i < num_cards - 2; i++) {
        if (is_exit_condition(i)) {
            break;
        }
        for (int j = i + 1; j < num_cards - 1; j++) {
            for (int k = j + 1; k < num_cards; k++) {
                int sum = cards[i] + cards[j] + cards[k];
                if (sum > target_num) {
                    break;
                }
                if (sum > max_sum) {
                    max_sum = sum;
                }
            }
        }
    }

    return max_sum;
}

int main(void)
{
    cin >> num_cards >> target_num;
    
    for (int i = 0; i < num_cards; i++) {
        cin >> cards[i];
    }
    
    cout << search();

    return 0;
}

Retrospect