백준 알고리즘 2798번: 블랙잭 C언어

문제 출처: https://www.acmicpc.net/problem/2798

2798번: 블랙잭

1. 코드

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int N, M, i, j, z, answer = 0, sum;
    int * card;
    
    scanf("%d %d", &N, &M);
    card = (int*) calloc(N, sizeof(int));
    
    for(i = 0; i < N; i++)
        scanf("%d", &card[i]);
    
    for(i = 0; i < N; i++)
    {
        for(j = i + 1; j < N; j++)
        {
            for(z = j + 1; z < N; z++)
            {
                sum = card[i] + card[j] + card[z];
                if(sum > answer && sum <= M)
                    answer = sum;
            }
        }
    }
    printf("%d", answer);
    free(card);
    return 0;
}

2. 문제 해결 방식

문제를 정리해보면 N과 M을 입력하고 카드의 값을 입력한 다음 카드 3개의 합이 M과 같거나 이하의 수를 출력하면 된다. 그렇다면 일단은 그것들을 입력할 수 있게 셋팅을 해야한다.

나는 N과 M을 선언하고 입력한 다음에 카드라는 포인터를 선언하여 stdlib.h 헤더 파일에 있는 calloc() 함수를 사용해서 동적할당을 하여 카드의 값을 입력받을 것이다.

int N, M, i, j, z, answer = 0, sum;
int * card;
    
scanf("%d %d", &N, &M);
card = (int*) calloc(N, sizeof(int));
    
for(i = 0; i < N; i++)
    scanf("%d", &card[i]);

이제 그 다음에는 한번 예시를 만들어보자. N의 값이 5이고, M의 값이 21이고, 카드의 값들은 5, 6, 7, 8, 9라고 할 때 카드의 조합은 다음과 같다.

조합	배열
5 6 7	[0 1 2]
5 6 8	[0 1 3]
5 6 9	[0 1 4]
5 7 8	[0 2 3]
5 7 9	[0 2 4]
5 8 9	[0 3 4]
6 7 8	[1 2 3]
6 7 9	[1 2 4]
6 8 9	[1 3 4]
7 8 9	[2 3 4]

그렇다면 순차적으로 배열이 늘어난다는 것을 볼 수 있는데 저는 이것을 반복문을 사용하여 표현해보겠습니다.

for(i = 0; i < N; i++)
{
    for(j = i + 1; j < N; j++)
    {
        for(z = j + 1; z < N; z++)
        {
        }
    }
}

그리고 마직막으로 이제 카드 3개의 값들을 더하고 M과 비교를 한 다음에 answer이라는 변수보다 값이 크다면 answer에 카드 3개의 합을 대입한다.

for(i = 0; i < N; i++)
{
    for(j = i + 1; j < N; j++)
    {
        for(z = j + 1; z < N; z++)
        {
            sum = card[i] + card[j] + card[z];
            if(sum > answer && sum <= M)
                answer = sum;
        }
    }
}

그리고 출력하고 메모리 할당한 것을 해제해주면 끝입니다.

printf("%d", answer);
free(card);