글 읽기 - 시간초과. 도저히 모르겠습니다. ㅜㅜ

kwooly 7년 전 0

아무리 생각해봐도, 아무리 고쳐도 풀리지가 않네요,

뭐가 문제일까요? ㅠㅠ

시간초과

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

static int cache[2001][2001];
static vector<int> *numbers;

static int Palindrome(int start, int end)
{
  if(start == end) return 1;
  if(start + 1 == end)
    return ((*numbers)[start] == (*numbers)[end]) ? 1 : 0;

  if(cache[start][end] != -1)
    return cache[start][end];

  return cache[start][end] = (*numbers)[start] == (*numbers)[end] ?
                                Palindrome(start + 1, end -1) : 0;
}

void Palindrome10942(
  vector<int> *_numbers,
  vector<pair<int,int>> *_queries,
  vector<int> *_output)
{
  int numberOfQueries = (*_queries).size();
  memset(cache, -1, sizeof(cache));
  numbers = _numbers;

  for(int i = 0; i < numberOfQueries; i++)
  {
    (*_output).push_back(
      Palindrome(
        (*_queries)[i].first - 1,
        (*_queries)[i].second - 1));
  }

  return;
}

int main()
{
  int i;
  int n;

  cin >> n;
  vector<int> numbers(n);

  for(i = 0; i < n; i++)
  {
    cin >> numbers[i];
  }

  cin >> n;
  vector<pair<int,int>> queries(n);

  for(i = 0; i < n; i++)
  {
    cin >> queries[i].first >> queries[i].second;
  }

  vector<int> actual;
  Palindrome10942(&numbers, &queries, &actual);


  for(i = 0; i < actual.size(); i++)
  {
    cout << actual[i] << endl;
  }

  return 0;
}

chogahui05 7년 전 1

출력을 한꺼번에 해 봅시다.

actual.size()번 돌면서 일일히 cout으로 출력하는 건 너무 느립니다.

kwooly 7년 전 0

우왓 감사합니다! vector의 size 함수 호출이 시간이 많이 걸리는 줄 몰랐네요.

말씀해주신 내용 + cin 대신 scanf로 바꾸어서 해결되었습니다.

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

문제

문제

출처

ICPC

시간초과. 도저히 모르겠습니다. ㅜㅜ

kwooly 7년 전 0

chogahui05 7년 전 1

kwooly 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말