백준 알고리즘 풀이 10942번 - 팰린드롬?

 

https://www.acmicpc.net/problem/10942

백준 알고리즘 10942번

10942번: 팰린드롬?

---

 

- 다이나믹 알고리즘(DP).

 

알고리즘

v[a][b] = a에서 b까지의 문자열의 팰린드롬 여부(a부터 b까지 문자열이 팰린드롬이라면 true, 아니라면 false)

팰린드롬이 될 조건

- a == b 라면 항상 팰린드롬.

- arr[a] == arr[b]인 경우에 팰린드롬.

- v[a+1][b-1] = true && arr[a]==arr[b]인 경우에 팰린드롬. 

---

 

예외 조건

b-a == 1 , arr[b]==arr[a]라면 팰린드롬이다.

 

소스코드

#include <iostream>
using namespace std;

int arr[2001];
bool v[2001][2001];
int main() 
{
	int arrSize,testCase;
	cin>>arrSize;
	for(int i=1;i<=arrSize;i++){
		scanf("%d",&arr[i]);
	}
	for(int i=1;i<=arrSize;i++){
		v[i][i]=true; 
		if(arr[i]==arr[i+1]) v[i][i+1]=true;
	}
	for(int i=2;i<=arrSize;i++){
		for(int j=1;j<=arrSize-i;j++){
			if(arr[j]==arr[j+i] && v[j+1][j+i-1]==true){
				v[j][i+j]=true;
			}
		}
	}
	cin>>testCase;
	for(int i=0;i<testCase;i++){
		int start,end;
		scanf("%d%d",&start,&end);
		printf("%d\n", v[start][end] ? 1 : 0);
	}
}

---

 

 

 

틀린 내용이나 지적 언제나 환영입니다.

도움이 되었다면 하트 한번씩 눌러주세요:)