글 읽기 - 시간초과 질문이여...

dayo05 3년 전 0

이 코드가 왜 시간초과일까요???

메모이제이션 나름 한다고 했는데... ㅎㅎ

using System;
using System.Diagnostics;
using System.IO;
using System.Text;

namespace ConsoleApp7
{
    class fivdat
    {
        public int zero;
        public int one;
        //public int dat;
        public fivdat()
        {
            zero = -1;
            one = -1;
            //dat = -1;
        }
    }
    class Program
    {
        static fivdat[] arr = new fivdat[41];
        static fivdat fiv(int val)
        {
            if (arr[val].zero != -1) return arr[val];
            fivdat rtn = new fivdat();
            if (val == 0)
            {
                //rtn.dat = 0;
                rtn.one = 0;
                rtn.zero = 1;
                return rtn;
            }
            else if (val == 1)
            {
                //rtn.dat = 1;
                rtn.one = 1;
                rtn.zero = 0;
                return rtn;
            }
            else
            {
                fivdat m1 = fiv(val - 1);
                fivdat m2 = fiv(val - 2);
                //rtn.dat = m1.dat + m2.dat;
                rtn.one = m1.one + m2.one;
                rtn.zero = m1.zero + m2.zero;
            }
            return rtn;
        }
        static void Main(string[] args)
        {
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i <= 40; i++) arr[i] = new fivdat();
            int t = int.Parse(sr.ReadLine());
            for(int i = 0; i < t; i++)
            {
                int n = int.Parse(sr.ReadLine());
                fivdat r = fiv(n);
                sb.AppendFormat("{0} {1}\n", r.zero, r.one);
            }
            sw.Write(sb);
            sw.Close();
        }
    }
}

dayo05 3년 전 0

보니깐 이 방법은 아예 불가능한거 같네요!

Coxie 3년 전 0

not

return rtn;

but

return arr[val] = rtn

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 질문이여...

dayo05 3년 전 0

dayo05 3년 전 0

Coxie 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말