글 읽기 - 시간 초과 오류...

lightseller 7년 전 0

일단 제가 작성한 알고리즘 자체는 O(n)이라 n <= 100k인 input에 대해서는 문제가 없을 거라고 생각합니다만 타임 오버가 뜨네요...

예상으로는 console에서 입력받고 split 하는 부분에서 타임 로스가 발생하고 있지 않나 싶은데 어떻게 개선해야 할 지 모르겠습니다;

찾아보니 bufferedstream 이 있다고는 하는데 이걸 어떻게 console에서의 입력과 결합시켜야 할지 모르겠습니다... 검색해도 잘 못 찾겠네요 ㅠㅠ

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace A
{
    class Program
    {
        public class TupleList<T1, T2, T3> : List<Tuple<int, int, string>>
        {
            public void Add(int item1, int item2, string s)
            {
                Add(new Tuple<int, int, string>(item1, item2, s));
            }
        }
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            
            for(int i = 0; i< n; i++)
            {
                int k = int.Parse(Console.ReadLine());

                int[,] input_arr = new int[k, 2];
                string[] first_input = Console.ReadLine().Split(' ');
                string[] second_input = Console.ReadLine().Split(' ');
                for (int x = 0; x< k; x++) // int.Parse()가 시간을 많이 잡아먹는다고 해서 변환해봤지만 효과x
                {
                    int y = 0;
                    for (int l = 0; l < first_input[x].Length; l++)
                        y = y * 10 + (first_input[x][l] - '0');
                    input_arr[x, 0] = y;
                }
                for (int x = 0; x < k; x++)
                {
                    int y = 0;
                    for (int l = 0; l < second_input[x].Length; l++)
                        y = y * 10 + (second_input[x][l] - '0');
                    input_arr[x, 1] = y;
                }

                decimal[,] cache = new decimal[k, 3];
                cache[0, 0] = input_arr[0, 0];
                cache[0, 1] = input_arr[0, 1];

                for(int j = 1; j< k; j++)
                {
                    cache[j, 0] = Math.Max(cache[j - 1, 1] + input_arr[j, 0], cache[j - 1, 2] + input_arr[j, 0]);
                    cache[j, 1] = Math.Max(cache[j - 1, 0] + input_arr[j, 1], cache[j - 1, 2] + input_arr[j, 1]);
                    cache[j, 2] = Math.Max(cache[j - 1, 0], cache[j - 1, 1]);
                }

                Console.WriteLine(Math.Max(Math.Max(cache[k - 1, 0], cache[k - 1, 1]), cache[k - 1, 2]));
            }

        }
    }
}

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

문제

문제

출처

ICPC

시간 초과 오류...

lightseller 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말