백준 2798번 : 블랙잭

1. 문제 분석

정해놓은 합보다 작거나 같은 카드 3장의 합을 구하기
입력: 카드의 개수, 3장의 합 기준
출력: 기준을 넘지 않는 3장의 합의 최댓값

2. 자료 구조 분석

정수 배열을 하나 썼다.
이유는 카드 3장의 합을 구하려면 element들을 저장해야 하는데
저장하는데 O(1)의 시간이 걸리기 때문이다.

3. 알고리즘 설명

1. 첫 번째 카드를 처음부터 끝까지 선택한다.
2. 두 번째 카드를 그 다음부터 끝까지 선택한다.
3. 세 번째 카드를 그 다음부터 끝까지 선택한다.
4. 선택한 카드 3장의 합이 현재 answer보다 크고, 기준보다 작거나 같으면 그 값을 교체한다.

4. 코드

#include <iostream>

using namespace std;

int main(){
    
    int valid_decks[3];
    int sum,num_of_cards;
    int candidate;
    int answer=0;
    cin>>num_of_cards>>sum;
    int cards[num_of_cards];

    for(int i=0;i<num_of_cards;i++){
        cin>>cards[i];
    }

    valid_decks[0]=cards[0];
    valid_decks[1]=cards[1];
    valid_decks[2]=cards[2];


    for(int i=0;i<num_of_cards-2;i++){
       for(int j=i+1;j<num_of_cards-1;j++){
           for(int k=j+1;k<num_of_cards;k++){
               candidate=cards[i]+cards[j]+cards[k];
               if(candidate>answer&&candidate<=sum){
                   answer=candidate;
               }

           }
       }
            
    }
    
    cout<<answer<<endl;
}

5. 분석

문제풀이에 사용된 알고리즘은 Brute-force 알고리즘이다.
for 문을 세 번을 돌고 있으므로 시간 복잡도는 O(N^3)이 될 것이고
사용된 자료구조는 N개의 숫자를 받는 배열 하나를 사용했으므로
공간 복잡도는 O(N)이 될 것이다.
더 좋은 방법이 있을까?