BOJ_2798 : 블랙잭 C

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

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장의 합을 출력한다.

예제 입력 1

5 21 5 6 7 8 9

예제 출력 1

21

 

이 문제는 공지를 잘 봐야한다.

https://www.acmicpc.net/board/view/47357

글 읽기 - ★☆★☆★ [필독] 블랙잭 FAQ ★☆★☆★

이 FAQ는 효율성에 상관 없이 이 문제를 푸는 것이 목적인 분들을 위해 작성되었습니다.
이 문제는 모든 경우의 수를 정직하게 따져보는 것이 의도인 문제입니다. 수행 시간을 줄이기 위한 묘기는 따로 필요하지 않습니다. 물론 실제로 시간 복잡도를 개선하는 것이 불가능한 것은 아니나, 문제의 제한인 N <= 100은 모든 가능한 세 카드의 조합을 1초 내에 뽑아보는 데에 전혀 무리가 없는 제한이기 때문에 전부 해보아도 되고, 반면에 증명할 수 없는 방법으로 탐색을 중도에 종료하도록 하는 것은 매우 위험합니다.예를 들어, 굳이 카드를 정렬할 필요가 없습니다. 어차피 모든 경우의 수를 따져볼 것이기 때문입니다.루프 중간에 break를 할 필요도 없습니다. 그것 때문에 따져보지 못하는 경우가 생깁니다.세 카드를 뽑는 로직을 다르게 할 필요도 없습니다. 예를 들어, 첫 두 장을 먼저 연속된 카드로 뽑아놓고 나머지 한 장을 루프를 돌려 찾는 방식으로 하면 틀립니다. 첫 두 장이 연속되지 않게 하는 것이 최적일 수도 있습니다. 세 장을 모두 같은 방법으로 뽑으세요.답 갱신은 세 장을 뽑았을 때마다 하면 됩니다. 굳이 분기를 나눠서 어떨 땐 갱신을 미루고, 다른 변수에 저장해보는 등 할 필요가 없습니다. "M을 넘지 않으면서 지금까지 찾았던 최댓값보다 크다면, 답을 갱신한다"를 모든 경우에 대해 똑같이 수행하면 됩니다.
요약하자면, 문제를 쉽고 단순하게 풀자는 것입니다. 어려운 기법이 동원될 필요가 없다면, 굳이 쓸 필요가 없습니다. 특히 그 방법이 최적이라는 것을 증명할 수 없다면, 아예 사용해서는 안 됩니다.

저 주황 하이라이트 부분이 포인트이다.

모든 가능한 세 카드 뽑아서 값을 갱신해주면 된다.

#include <stdio.h>
int main(void){
    int arr[100]={0,};
    int n,i,bj,j,k,ama_big=0,temp;
    scanf("%d %d", &n, &bj);
    for(i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    for(i=0;i<100;i++)
    {
        for(j=0;j<100;j++)
        {
            for(k=0;k<100;k++)
            {
                if(arr[i]+arr[j]+arr[k]>bj)
				{//BJ보단 작으면서
                continue;
                }
                else{
					if(arr[i]==arr[j])//같거나1
					{
						continue;
					}
					if(arr[j]==arr[k])//같거나2
					{
						continue;
					}
					if(arr[i]==arr[k])//같거나3
					{
						continue;
					}
					if(arr[i]==0)//0이거나1
					{
						continue;
					}
					if(arr[j]==0)//0이거나2
					{
						continue;
					}
					if(arr[k]==0)//0이거나3
					{
						continue;
					}
                    temp=arr[i]+arr[j]+arr[k];
                    if(temp>ama_big)//AMA_BIG보다 크면 AMABIG에 저장.
                    {
                    ama_big=temp;
                    //printf("%d / %d / %d ama_big: %d\n",arr[i],arr[j],arr[k],ama_big);
                    }
                }
            }
        }
    }
    printf("%d",ama_big);
    return 0;
}

#include <stdio.h>

int main(void){

int arr[100]={0,}; //배열은 백칸. 백개이기에. 숫자라서 널문자는 필요없음.

int n,i,bj,j,k,ama_big=0,temp; // AMA_BIG : 아마 클것으로 예상되는 수.

scanf("%d %d", &n, &bj); //카드의 수와 BJ 숫자를 입력받는다.

for(i=0;i<n;i++) //N번 포문을 돌려 배열에 숫자를 입력받고

{

scanf("%d",&arr[i]);

}

for(i=0;i<100;i++) //첫번째

{

for(j=0;j<100;j++)//두번째

{

for(k=0;k<100;k++) //세번째 포문을 만들어서 가능한 모든 조합을 돌려볼껀데

{

if(arr[i]+arr[j]+arr[k]>bj)

                {//BJ보단 작으면서

continue;

}

else{

                    if(arr[i]==arr[j])// 첫번째 카드와 같거나

                    {

                        continue;

                    }

                    if(arr[j]==arr[k])//두번째와 같거나

                    {

                        continue;

                    }

                    if(arr[i]==arr[k])//세번째와 같으면 넘어가고

                    {

                        continue;

                    }

                    if(arr[i]==0)//0이거나

                    {

                        continue;

                    }

                    if(arr[j]==0)//0이거나

                    {

                        continue;

                    }

                    if(arr[k]==0)//0이 나오면 이것도 넘어가고

                    {

                        continue;

                    }

temp=arr[i]+arr[j]+arr[k]; 위 필터를 모두 통과한 수만 TEMP에 저장해서

if(temp>ama_big)//AMA_BIG보다 크면 AMABIG에 저장.

{

ama_big=temp;

//printf("%d / %d / %d ama_big: %d\n",arr[i],arr[j],arr[k],ama_big); //디버깅하려고 놔둔 문장이다. 

}

}

}

}

}

printf("%d",ama_big); //AMA_BIG을 출력해주면 끝난다.

return 0;

}