백준 2798(참고) 개인공부 ----c++

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

2798번: 블랙잭

풀이

이 문제의 핵심은 n장의 카드에 써져 있는 숫자가 주어졌을 때, m을 넘지 않으면서 m에 최대한 가까운 카드 3장의 합을 구하는 것이다.

 

ex) 5장의 카드가 주어지고 카드m(21)이 주어진다.

5장의 카드 5,6,7,8,9가 주어지면 m(21)에 최대한 가까운수를 만들수 있는 3장은 6,7,8이다.

 

 

코드

#include <iostream>
 
using namespace std;
 
int main() {
 
    int a[101]={0,};    
    int n;
    int target;
    int max=0;
    int sum=0;
 
    cin>>n>>target;
 
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
 
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            for(int k=j+1; k<n; k++){
                sum=a[i]+a[j]+a[k];
                if(sum<=target&&sum>max)
                max=sum;
            }
        }
    }
 
    cout<<max;
}

 

풀이 2

1. 일단 배열로 n장의 카드를 입력받고

2. 3개의 중접 for문으로 카드m의 대한 3장의 카드 경우의 수를 알아낸다.

3. 첫번째 수를 정하기위한 코드 for(int i=0; i<n; i++)

4. 첫번째 수가 정해졌으면 다음 for문은 첫번째수를 제외한 2번째 수를 정한다. for(int j=i+1; j<n; j++)

5. 1,2번째 수가 정해지고 1,2번째 수를 제외한 나머지 수를 알아내는 for문을 작성한다. for(int k=j+1; k<n; k++)

6. k for문에서 이 식으로 검사를 한다.if(sum<=target&&sum>max)

                                                max=sum;

7. sum값이 m(target)값보다 작거나 같아야 하고 만약 같지 않을시에 m(target)에 최대한 가까운 sum값을 찾는다.

 

정리

이 문제를 풀기 위해서는 3장의 카드를 고르기위한 다중for문을 이해하는것이 가장 중요한것 같다.