글 읽기 - 반례가 없는거 같은데.. 왠만한거 다 돌려봄.

coco145 3년 전 0

반례가 없는거 같은데.. 왠만한거 다 돌려봤는데... 왜 틀렸다고 나올까요...
혹쉬 고수님들 한번 봐주실수 있을까요...
로직으로는 3개 단위로 최대값 찾고 인접한 최대값 더해서 솔루션 구하는 로직입니다.
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace Tetromino2
{
    class Program
    {
        static int[] ValueArrayFromIndex;
        static bool[] VisitArrayFromIndex;

        static Dictionary<int, List<int>> AdjacentListDictionaryFromIndex = new Dictionary<int, List<int>>();
        static Dictionary<int, List<string>> StringListDictionaryFromThreeGroupSum = new Dictionary<int, List<string>>();

        static StreamReader streamReader = new StreamReader(Console.OpenStandardInput());
        static StreamWriter streamWriter = new StreamWriter(Console.OpenStandardOutput());

        static void Main(string[] args)
        {
            streamWriter.AutoFlush = true;

            string[] SplitString = streamReader.ReadLine().Split(' ');
            int WidthCount = Convert.ToInt32(SplitString[1]);
            int HeightCount = Convert.ToInt32(SplitString[0]);
            int MaxNodeNumber = WidthCount * HeightCount - 1;

            if (WidthCount < 4 || HeightCount < 4 || WidthCount > 500 || HeightCount  > 500)
                return;

            InitializeNodeInfomation(WidthCount, HeightCount);


            for (int index = 0; index < HeightCount * WidthCount; index++)
            {
                CheckMaximumSumFromIndex(index);
            }

            int originMaximumSum = MaximumSum;

            foreach (var NodeNumberString in StringListDictionaryFromThreeGroupSum[MaximumSum])
            {
                string[] SplitString2 = NodeNumberString.Split(' ');

                for (int i = 0; i < 3; i++)
                {
                    foreach (var AdjacentIndex in AdjacentListDictionaryFromIndex[Convert.ToInt32(SplitString2[i])])
                    {
                        if (AdjacentIndex != Convert.ToInt32(SplitString2[0]) && AdjacentIndex != Convert.ToInt32(SplitString2[1]) &&
                            AdjacentIndex != Convert.ToInt32(SplitString2[2]))
                        {
                            MaximumSum = originMaximumSum + ValueArrayFromIndex[AdjacentIndex];
                        }
                    }
                }
            }

            streamWriter.WriteLine(MaximumSum);
        }

        private static void CheckMaximumSumFromIndex(int index)
        {
            VisitArrayFromIndex[index] = true;

            List<string> CheckListForSearchingMaximumSum = new List<string>();

            int FirstIndex = index;

            foreach (var AdjacentIndexSecond in AdjacentListDictionaryFromIndex[index])
            {
                if (!VisitArrayFromIndex[AdjacentIndexSecond])
                {
                    int SecondIndex = AdjacentIndexSecond;

                    foreach (var AdjacentIndexThird in AdjacentListDictionaryFromIndex[SecondIndex])
                    {
                        if (!VisitArrayFromIndex[AdjacentIndexThird])
                        {
                            int ThirdIndex = AdjacentIndexThird;
                            CheckListForSearchingMaximumSum.Add(MakeGroupStringFromIndex(FirstIndex, SecondIndex, ThirdIndex));
                        }    
                    }
                }
            }

            foreach(var ThreeGroupString in CheckListForSearchingMaximumSum)
                SetMaximumValueAndStringListDictionaryFromThreeGroupSum(ThreeGroupString);

        }

        static string MakeGroupStringFromIndex(int A, int B, int C)
        {
            return A + " " + B + " " + C;
        }

        static int SumFromGroup(int AIndex, int BIndex, int CIndex)
        {
            return ValueArrayFromIndex[AIndex] + ValueArrayFromIndex[BIndex] + ValueArrayFromIndex[CIndex];
        }

        private static void InitializeNodeInfomation(int WidthCount, int HeightCount)
        {
            ValueArrayFromIndex = Enumerable.Repeat<int>(0, WidthCount * HeightCount).ToArray<int>();
            VisitArrayFromIndex = Enumerable.Repeat<bool>(false, WidthCount * HeightCount).ToArray<bool>();

            InitializeAdjacentDictionaryAndValueArray( WidthCount,  HeightCount);
        }

        private static void InitializeAdjacentDictionaryAndValueArray(int WidthCount, int HeightCount)
        {
            int MaxNodeNumber = WidthCount * HeightCount - 1;

            for (int ColumnIndex = 0; ColumnIndex < HeightCount; ColumnIndex++)
            {
                string[] SplitString1 = streamReader.ReadLine().Split(' ');

                for (int RowIndex = 0; RowIndex < WidthCount; RowIndex++)
                {
                    int NodeIndex = ColumnIndex * WidthCount + RowIndex;

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

                    if (NodeIndex - WidthCount >= 0)
                        AdjacentNodeList.Add(NodeIndex - WidthCount);
                    if (NodeIndex + WidthCount <= MaxNodeNumber)
                        AdjacentNodeList.Add(NodeIndex + WidthCount);

                    if (RowIndex == 0)
                    {
                        AdjacentNodeList.Add(NodeIndex + 1);
                    }
                    else if (RowIndex == WidthCount - 1)
                    {
                        AdjacentNodeList.Add(NodeIndex - 1);
                    }
                    else
                    {
                        AdjacentNodeList.Add(NodeIndex + 1);
                        AdjacentNodeList.Add(NodeIndex - 1);
                    }

                    if (Convert.ToInt32(SplitString1[RowIndex]) < 1 || Convert.ToInt32(SplitString1[RowIndex]) > 1000)
                        return;

                    ValueArrayFromIndex[NodeIndex] = Convert.ToInt32(SplitString1[RowIndex]);
                    AdjacentListDictionaryFromIndex[NodeIndex] = AdjacentNodeList;
                }
            }
        }

        static void SetMaximumValueAndStringListDictionaryFromThreeGroupSum(string ThreeGroupString)
        {
            string[] splitString = ThreeGroupString.Split(' ');
            int Sum = SumFromGroup(Convert.ToInt32( splitString[0]), Convert.ToInt32(splitString[1]), Convert.ToInt32(splitString[2]));

            if (Sum > MaximumSum)
            {
                MaximumSum = Sum;

                StringListDictionaryFromThreeGroupSum.Clear();
                StringListDictionaryFromThreeGroupSum[MaximumSum] = new List<string>();
                StringListDictionaryFromThreeGroupSum[MaximumSum].Add(ThreeGroupString);
            }
            else if (Sum == MaximumSum)
            {
                StringListDictionaryFromThreeGroupSum[MaximumSum].Add(ThreeGroupString);
            }

        }

        static public int maximumSum = -1;
        static public int MaximumSum
        {
            get { return maximumSum; }
            set
            {
                if (value > maximumSum)
                {
                    maximumSum = value;
                }
            }
        }
    }
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

반례가 없는거 같은데.. 왠만한거 다 돌려봄.

coco145 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
