문제
접근 방안
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;
}
