[2798] 블랙잭

입력
첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.
합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력
첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

생각

복잡하게 생각하지 않고 그냥 선형 순차탐색으로 구현할 예정이다. BFS나 DFS는 관련된 파트 가면 연습할 예정. O(n^3) 으로 예상한다.

• 필요한 변수
  - int n, m
  • string cards //둘째 줄에 입력받는 카드에 써진 수들 (한 줄이니까 Console.ReadLine()써도 될것같다.)
  • int sum //합 저장할 변수
  • int[] nums //세 변수 저장할 어레이
• 필요한 메소드
  • void blackJack(int m, int[] nums) //세 변수 합을 구해서 m과 가장 가까운 sum을 매번 갱신한 뒤, 탐색이 끝나면 sum을 Console.WriteLine()하는 메소드
• 주의사항
  • m을 입력받고 nums의 크기를 초기화 해야함
  • 빨리 끝내려면 m과 동일한 합을 구하면 바로 종료하도록 코드 작성

첫시도

using System.Text;
using System;

namespace BaekJoon
{
    public class P2798
    {
        int n;
        int m;
        int sum;
        int[] nums;

        P2798(int n, int m, int[] nums) {
            this.n = n;
            this.m = m;
            this.nums = nums;
            sum = 0;

        }

        void blackJack()
        {
            int set;
            for(int a = 0; a < nums.Length-2; a++)
            {
                for(int b = 1; b < nums.Length-1; b++)
                {
                    for(int c = 2; c < nums.Length; c++)
                    {
                        set = nums[a] + nums[b] + nums[c];
                        if (Math.Abs(set - m) < Math.Abs(sum - m))
                        {
                            sum = set;
                        }
                    }
                }
                if (sum == m) break;
            }
            Console.WriteLine(sum);
        }
        static void Main(string[] args)
        {
            string s = Console.ReadLine();
            string cards = Console.ReadLine();

            string[] ss = s.Split();
            string[] ss2 = cards.Split();

            int[] num = new int[ss2.Length];
            for(int i = 0;  i < ss2.Length; i++)
            {
                num[i] = int.Parse(ss2[i]);
            }
            P2798 p = new(int.Parse(ss[0]), int.Parse(ss[1]),num);
            
            p.blackJack();
        }
    }

}

ㅋㅋㅋㅋㅋㅋㅋ

틀린 이유

if (Math.Abs(set - m) < Math.Abs(sum - m))
이걸 보면 주어진 숫자 m을 넘어도 가까운 수이기만 하면 정답처리가 되어버린다.
그래서 틀렸다.
또한

        void blackJack()
       {
           int set;
           for(int a = 0; a < nums.Length-2; a++)
           {
               for(int b = 1; b < nums.Length-1; b++)
               {
                   for(int c = 2; c < nums.Length; c++)
                   {
                       set = nums[a] + nums[b] + nums[c];
                       if (set<=m && set > sum)
                       {
                           sum = set;
                       }
                   }
               }
           }
           Console.WriteLine(sum);
       }

여기 보면 a = 0, b = 1, c = 2 인데, 이렇게 되면 동일한 수를 중복으로 합산한다. a = 0, b = a + 1, c = b+1 이런 식으로 고쳐야 한다.

결과

using System;

namespace BaekJoon
{
    public class P2798
    {
        int n;
        int m;
        int sum;
        int[] nums;

        P2798(int n, int m, int[] nums) {
            this.n = n;
            this.m = m;
            this.nums = nums;
            sum = 0;

        }

        void blackJack()
        {
            int set;
            for(int a = 0; a < nums.Length-2; a++)
            {
                for(int b = a + 1; b < nums.Length-1; b++)
                {
                    for(int c = b + 1; c < nums.Length; c++)
                    {
                        set = nums[a] + nums[b] + nums[c];
                        if (set<=m && set > sum)
                        {
                            sum = set;
                        }
                    }
                }
            }
            Console.WriteLine(sum);
        }
        static void Main(string[] args)
        {
            string s = Console.ReadLine();
            string cards = Console.ReadLine();

            string[] ss = s.Split();
            string[] ss2 = cards.Split();

            int[] num = new int[ss2.Length];
            for(int i = 0;  i < ss2.Length; i++)
            {
                num[i] = int.Parse(ss2[i]);
            }
            P2798 p = new(int.Parse(ss[0]), int.Parse(ss[1]),num);
            
            p.blackJack();
        }
    }

}

못 한 부분

• n은 사용하지 않는데 변수로 선언해둠
• 이미 답이 나왔을 경우에도 종료하지 않고 모든 경우를 탐색함.