백준 2798번 : 블랙잭
1. 문제 분석
정해놓은 합보다 작거나 같은 카드 3장의 합을 구하기
입력: 카드의 개수, 3장의 합 기준
출력: 기준을 넘지 않는 3장의 합의 최댓값
2. 자료 구조 분석
정수 배열을 하나 썼다.
이유는 카드 3장의 합을 구하려면 element들을 저장해야 하는데
저장하는데 O(1)의 시간이 걸리기 때문이다.
3. 알고리즘 설명
- 첫 번째 카드를 처음부터 끝까지 선택한다.
- 두 번째 카드를 그 다음부터 끝까지 선택한다.
- 세 번째 카드를 그 다음부터 끝까지 선택한다.
- 선택한 카드 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)이 될 것이다.
더 좋은 방법이 있을까?
Author And Source
이 문제에 관하여(백준 2798번 : 블랙잭), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@onebellfortune/백준-2798번-블랙잭저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)