[백준] 10942 - 팰린드롬?

1. 문제

10942번: 팰린드롬?

2. 개요

자연수 N개로 이루어진 수열이 주어진다.

S, E로 이루어진 M개의 질문이 주어지는데,

수열의 S번째 수 부터 E번째 수 까지의 부분수열이 팰린드롬이라면 1을 아니라면 0을 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

2차원배열 dp를 -1로 초기화하고 진행한다.

dp[i][j] 는 i ~ j인 부분수열이 팰린드롬인지 아닌지 여부를 나타낼 것이다.

따라서 i == j인 경우는 무조건 팰린드롬이므로 이 때는 1로 값을 갱신해준다.

일단 S번째 수와 E번째 수가 다르다면 팰린드롬이 될 수 없다.

만약 같다면 S+1 ~ E-1이 팰린드롬이라면 팰린드롬이 된다.

이를 재귀적으로 풀어내 dp테이블을 채우고 값을 출력해주면 된다.

이때 E == S+1 이라면 위 방법으로 비교가 불가능하므로 직접 비교하여 팰린드롬 여부를 판단한다.

3-2. Python

import sys

sys.setrecursionlimit(100000000)

def makedp(s, e):
    if dp[s][e] != -1:
        return dp[s][e]

    if s == e:
        return 1

    elif s + 1 == e:
        if nums[s-1] == nums[e-1]:
            dp[s][e] = 1
        
        else:
            dp[s][e] = 0

    elif nums[s-1] != nums[e-1]:
        dp[s][e] = 0

    else:
        dp[s][e] = makedp(s+1, e-1)

    return dp[s][e]

N = int(sys.stdin.readline())

nums = list(map(int, sys.stdin.readline().split()))

M = int(sys.stdin.readline())

dp = [[-1 for i in range(N + 1)] for j in range(N + 1)]

for i in range(1, N + 1):
    dp[i][i] = 1

for i in range(M):
    S, E = map(int, sys.stdin.readline().split())

    k = makedp(S, E)
    print(k)

3-3. C#

using System.Text;

namespace boj_10942
{
    internal class Program
    {
        static int[,] dp;
        static int[] nums;
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int N = int.Parse(sr.ReadLine());

            nums = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);

            int M = int.Parse(sr.ReadLine());

            dp = new int[N + 1, N + 1];

            for (int i = 0; i < N + 1; i++)
            {
                for (int j = 0; j < N + 1; j++)
                {
                    if (i == j)
                        dp[i, j] = 1;
                    else
                        dp[i, j] = -1;
                }
            }

            for (int i = 0; i < M; i++)
            {
                string[] input = sr.ReadLine().Split();
                int S = int.Parse(input[0]);
                int E = int.Parse(input[1]);

                sw.WriteLine(Makedp(S, E));
            }

            sr.Close();
            sw.Close();
        }

        static int Makedp (int s, int e)
        {
            if (dp[s, e] != -1)
                return dp[s, e];

            if (s + 1 == e)
            {
                if (nums[s - 1] == nums[e - 1])
                    dp[s, e] = 1;
                else
                    dp[s, e] = 0;
            }

            else if (nums[s - 1] != nums[e - 1])
                dp[s, e] = 0;

            else
                dp[s, e] = Makedp(s + 1, e - 1);

            return dp[s, e];
        }
    }
}

C# 의 경우에는 구현한 코드가 구려선지 Console.ReadLine() 과 WriteLine()을 이용하면 시간초과다.

StreamReader와 StreamWriter를 이용한 입출력으로 변경하니 통과했다.