백준 10942번 팰린드롬

문제

접근 방안

dp문제이다.

처음 dp로 하지 않고 구현으로 하였다 틀렸다.

틀린 코드

#include "stdafx.h"
#include <iostream>
using namespace std;

int main()
{
    int input, input2;
    cin >> input;
    int arr[2001] = { 0, };
    for (int i=1; i<=input; i++) {
        cin >> arr[i];
    }
    cin >> input2;
    int *arr2 = new int[input2];
    int s,e,k=0,b=1;
    for (int i = 0; i < input2; i++) {
        b = 1;
        cin >> s >> e;
        while (s != e && s < e) {
            if (arr[s] != arr[e]) {
                b = 0;
                break;
            }
            s++;
            e--;
        }
        arr2[k] = b;
        k++;
    }
    for (int i = 0; i < input2; i++)
        cout << arr2[i]<<endl;

    return 0;
}

틀린 코드의 풀이 방식은 홍준이가 명준이에게 물어볼떄마다 일일이 아닌지 맞는지 찾았다.

당연히 시간초과. 이 문제의 핵심은 0.5초이다.

풀이방법

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

즉 i와 i+j가 같은데 그 사이 값이 팰린드롬이면 i~i+j까지는 팰린드롬이라는 의미이다.

문제에서 실수한 부분

cin, cout을 쓰면 시간 초과가 되어 printf, scanf를 써야한다.

scanf_s, printf_s로 하면 컴파일 에러가 나니 scanf,printf로 쓰도록 한다.

코드

#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    int input, input2;
    scanf("%d", &input);
    int arr[2001] = { 0, };

    for (int i = 1; i <= input; i++) {
        cin >> arr[i];
    }

    int s, e, k = 0, b = 1;
    int **dp;
    int c, l;
    dp = new int *[input + 1];
    for (int i = 0; i <= input; i++) {
        dp[i] = new int[input + 1]();
    }

    for (int i = 1; i < input; i++) {
        dp[i][i] = 1;
        if (arr[i] == arr[i + 1])dp[i][i + 1] = 1;
    }
    dp[input][input] = 1;
    int x = 1;
    for (int j = 2; j <= (input - 1); j++) {
        for (int i = 1; i <= (input - j); i++) {
            if (arr[i] == arr[i + j]&&dp[i+1][i+j-1])
                dp[i][i + j] = 1;
        }
    }

    cin >> input2;
    int *arr2 = new int[input2];

    for (int i = 0; i < input2; i++) {
        scanf("%d %d", &s, &e);
        printf("%d\n", dp[s][e]);
    }
    return 0;
}