코딩테스트 준비 - 블랙잭

혼자서 다시푸는 코딩테스트 준비 일지 - 31

브루트포스

Oct 1

6 min read

다시푸는 코딩 테스트 준비 일지

응시 사이트 : BOJ
문제 : 2798.블랙잭
사용언어 : C#
난이도 : 중
풀이시간 : 14m
유형 : 브루트포스

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 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

예제 입력 2

10 500
93 181 245 214 315 36 185 138 216 295

예제 출력 2

문제 풀이 접근

오늘은 그래프를 한동안 풀어서, 다른 유형을 풀어볼까 생각하게 되었고 바로 보인게 브루트포스(완전탐색) 이었다.

처음이라 난이도가 낮았으나, 그래도 생각을 조금은 하게되었다.

문제의 요구는 블랙잭은 21까지 가장 가까운 숫자 조합을 만드는게 승리자이지만, 문제에서 타겟 넘버를 줄거고, 그 넘버를 만들 수 있는 가장 가까운 숫자를 만들어서 제출하면 된다.

이전에는, 맞춘다해서 함수를 종료하지 않았는데, 아티클을 작성하면서 그럼 가장 가까운 숫자면 더 빠르게 찾아낼 수 있다는 생각이 들어서 맞으면 바로 출력하고 함수 종료했더니, 4ms정도 더 빨라졌다.

모든 루프를 다 순회하는 것 보다 이쪽이 더 그리디하게 풀 수 있을것이라고 생각한다.

정답 작성 코드 (C#)

using System;
using System.CodeDom;
using System.Collections.Generic;
using System.ComponentModel;
using System.ComponentModel.Design;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Security.AccessControl;
using System.Security.Authentication;
using System.Security.Cryptography;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Web;
using System.Xml.Linq;
using static CodingTestProj.Program;

/*
 * Difficulty : Easy
 * URL : https://www.acmicpc.net/problem/2798
 */


namespace CodingTestProj
{
    internal class Program
    {


        static void Main(string[] args)
        {
            Solution solution = new Solution();
            solution.solve();
        }
    }
    public class Solution
    {
        public int n;
        public int m;

        public int balance;
        public int ret;

        public void solve()
        {
            ret = 0;
            balance = int.MaxValue;
            var input = Console.ReadLine().Split(' ');
            n = Int32.Parse(input[0]);
            m = Int32.Parse(input[1]);

            List<int> list = new List<int>();

            input = Console.ReadLine().Split(' ');

            for (int i = 0; i < input.Length; ++i)
            {
                list.Add(Int32.Parse(input[i]));
            }

            for (int i = 0; i < list.Count; ++i)
            {
                for (int j = i + 1; j < list.Count; ++j)
                {
                    for (int k = j + 1; k < list.Count; ++k)
                    {

                        var value1 = list[i];
                        var value2 = list[j];
                        var value3 = list[k];

                        var sum = value1 + value2 + value3;

                        if (sum > m) continue;

                        var checkRet = Math.Abs(sum - m);



                        if (checkRet < balance)
                        {
                            balance = checkRet;
                            ret = sum;
                        }

                        if (checkRet == 0)
                        {
                            ret = sum;
                            Console.WriteLine(ret);
                            return;
                        }
                    }
                }
            }

            Console.WriteLine(ret);
        }
    }
}