백준 2798 응용: 카드 4장을 뽑아 근접한 합 구하기

오늘은 오늘 풀었던 백준 2798번 문제(블랙잭)를 응용해서,
카드 4장을 뽑아 목표값 M을 넘지 않으면서 가장 큰 합을 구하는 문제를 직접 만들어 풀어보았다.

🧠 문제 요약

N장의 카드 중 4장을 골라 합을 구한다.

이 합이 M 이하이면서 가장 큰 합이 되도록 한다.

단, 같은 카드는 중복해서 뽑지 않는다.

🔍 문제 접근 방식

4중 for문을 사용해 모든 조합을 순회한다.
(i < j < k < l 조건을 지키면 중복 없이 모든 조합을 순회 가능)

조건을 만족할 경우, 합과 함께 사용한 카드 4장도 저장한다.

최종적으로 가장 큰 합과 그에 해당하는 카드 4장을 출력한다.

using System;

namespace backjoon
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string[] nm = Console.ReadLine().Split();
            int n = int.Parse(nm[0]);
            int m = int.Parse(nm[1]);

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

            int max = 0;
            int[] answer = new int[4]; // 가장 근접한 합의 카드 조합 저장용

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

                            if (sum <= m && sum > max)
                            {
                                max = sum;
                                answer[0] = cards[i];
                                answer[1] = cards[j];
                                answer[2] = cards[k];
                                answer[3] = cards[l];
                            }
                        }
                    }
                }
            }

            Console.WriteLine(max);
            Console.WriteLine(string.Join(" ", answer));
        }
    }
}

✨ 출력 예시
입력:

5 100  
20 40 30 50 10

출력:

100  
20 30 40 10

📌 배운 점
중복 없이 조합을 고르기 위해서는 i < j < k < l 순서로 루프를 구성해야 한다.

조건을 만족하는 조합의 정보를 같이 저장하면, 나중에 어떤 카드로 만들었는지 확인 가능하다.

이렇게 단순한 브루트포스 방식도 문제를 잘 이해하고 적용하면 효과적으로 사용할 수 있다.

🧭 느낀 점
오늘 3장 뽑는 문제를 풀었을 땐 for문 구조가 헷갈렸는데,
이번에는 4장으로 확장하면서 구조를 완전히 이해하게 되었다.
직접 문제를 살짝 변형해서 만들어보니 더 기억에 잘 남는 것 같다.