백준 10942번 팰린드롬?

문제 링크입니다: https://www.acmicpc.net/problem/10942

scanf와 printf가 cin과 cout보다 얼마나 빠른지 실감할 수 있는 문제였습니다.

실제로 함수 코드는 똑같은데 배열을 입력받을 때 cin으로 받으면 시간초과가 발생했고 scanf로 받으면 시간초과가 발생하지 않았습니다.

팰린드롬은 우선 양 끝이 같아야하므로 양 끝이 같은지를 확인하고 처음과 마지막 인덱스를 하나씩 줄여가며 재귀함수를 통해 해결해도 되고 비재귀함수를 통해 해결해도 됩니다.

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 2000;

 

int N, M;

int arr[MAX + 1];

//int cache[MAX + 1][MAX + 1];

bool cache[MAX + 1][MAX + 1];

 

//재귀

/*

int palindrome(int start, int end)

{

        //기저사례

        if (start >= end)

               return 1;

        int &result = cache[start][end];

        if (result != -1)

               return result;

        //양 끝이 같지 않다면 팰린드롬 아님

        if (arr[start] != arr[end])

               return result = 0;

        return result = palindrome(start + 1, end - 1);

}

*/

 

//비재귀

void palindrome(void)

{

        //길이 1

        for (int i = 1;i <= N; i++)

               cache[i][i] = true;

        //길이 2

        for (int i = 1; i < N; i++)

               if (arr[i] == arr[i + 1])

                       cache[i][i + 1] = true;

        //길이 3 이상

        for (int i = 2; i < N; i++)

               for (int j = 1; j <= N - i; j++)

                       //앞 뒤가 같고, 앞 뒤 사이에 있는 수들이 팰린드롬인 경우

                       if (arr[j] == arr[j + i] && cache[j + 1][j + i - 1])

                              cache[j][j + i] = true;

}

 

 

int main(void)

{

        cin >> N;

        for (int i = 1; i <= N; i++)

               scanf("%d", &arr[i]);

 

        cin >> M;

        memset(cache, false, sizeof(cache));

        palindrome();

        //memset(cache, -1, sizeof(cache));

 

        for (int i = 0; i < M; i++)

        {

               int S, E;

               scanf("%d %d", &S, &E); //start, end

               //printf("%d\n", palindrome(S, E));

               printf("%d\n", cache[S][E]);

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~