12849번. 본대산책(실버1)

https://www.acmicpc.net/problem/12849

 

처음 문제풀이시에 DFS를 활용하여 문제를 풀었으나 시간초과가 나왔다. DP를 활용하여 2차원배열([시간, 건물번호])로 계산하면 된다.

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _12849
{
    class Program
    {
        public static int time;
        //public static int count = 0;
        public static int[,] iMap = new int[,] { { 0, 1, 1, 0, 0, 0, 0, 0 },
                                                 { 1, 0, 1, 1, 0, 0, 0, 0 },
                                                 { 1, 1, 0, 1, 1, 0, 0, 0 },
                                                 { 0, 1, 1, 0, 1, 1, 0, 0 },
                                                 { 0, 0, 1, 1, 0, 1, 0, 1 },
                                                 { 0, 0, 0, 1, 1, 0, 1, 0 },
                                                 { 0, 0, 0, 0, 0, 1, 0, 1 },
                                                 { 0, 0, 0, 0, 1, 0, 1, 0 } };
        public static int[,] DP = new int[100001, 8];

        public static void DPCalcu()
        {
            for(int i = 1; i <= time; i++)
            {
                for(int j = 0; j < 8; j++)
                {
                    if(DP[i-1, j] > 0)
                    {
                        for(int k = 0; k < 8; k++)
                        {
                            DP[i, k] = DP[i, k] + iMap[j, k] * DP[i-1, j];
                            DP[i, k] = DP[i, k] % 1000000007;
                        }
                    }
                }
            }
        }


        // 시간초과
        //public static void DFS(int start, int r_time)
        //{
        //    if(time < r_time)
        //    {
        //        return;
        //    }

        //    if(time == r_time)
        //    {
        //        if(start == 0)
        //        {
        //            count++;
        //            if (count == 1000000007)
        //            {
        //                count = 0;
        //            }
        //            return;
        //        }
        //        else
        //        {
        //            return;
        //        }
        //    }

        //    for(int i = 0; i < 8; i++)
        //    {
        //        if(iMap[start,i] == 1)
        //        {
        //            DFS(i, r_time + 1);
        //        }
        //    }
        //}

        static void Main(string[] args)
        {
            time = int.Parse(Console.ReadLine());

            DP[0, 0] = 1;

            DPCalcu();
            Console.WriteLine(DP[time, 0]);

            //시간초과
            //DFS(0, 0);
            //Console.WriteLine(count);
        }
    }
}

 

예제1)

10

답 : 9857

 

채점 결과 창