백준 2798 C#) 블랙잭

브루트포스 단계의 첫 문제인 만큼 어렵지 않게 풀 수 있다.

 

public static class PS
{
    private readonly static int n, m;
    private static int[] cards;

    static PS()
    {
        string[] nm = Console.ReadLine().Split();
        n = int.Parse(nm[0]);
        m = int.Parse(nm[1]);

        cards = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    }

    public static void Main()
    {
        int max = 0;
        int sum;

        for (int i = 0; i < n - 2; i++)
        {
            for (int j = i + 1; j < n - 1; j++)
            {
                for (int k = j + 1; k < n; k++)
                {
                    sum = cards[i] + cards[j] + cards[k];

                    if (sum <= m && sum > max)
                        max = sum;
                }
            }
        }

        Console.Write(max);
    }
}

 

브루트포스 알고리즘은 모든 경우의 수를 체크하는 알고리즘이다.

즉, 이 문제도 모든 경우의 수를 체크해야 한다.

 

우선 n장의 카드 중에서 3장을 뽑아야 하므로 3중 for문을 사용했다.

중복된 조합은 당연히 체크할 필요가 없으므로 인덱스는 증가 수열이 될 것이다.

그렇게 뽑은 3장의 카드를 모두 더하고, m 이하이면서 m에 가장 가까운 지를 체크하면 되는 간단한 문제였다.

 

그러나...

이 문제는 3장이라고 못을 박아놨기 때문에 가벼운 마음으로 3중 for문을 사용할 수 있었으나

만약 10장, 100장, 1000장이라면...?

그때는 dfs를 활용해야 할 것이다.