[백준] No.10942 - 팰린드롬? (C++)

문제

www.acmicpc.net/problem/10942

10942번: 팰린드롬?

 

풀이

팰린드롬이란 거꾸로 읽어도 동일한 회문을 의미한다.

 

start번째 수부터 end번째 수까지가 팰린드롬임을 확인하려면 

일단 arr[start]와 arr[end]가 같아야 한다.

 

그 후 arr[start+1]에서 arr[end-1] 까지가 팰린드롬이라면 해당 수열은 팰린드롬임을 알 수 있다.

 

즉, arr[start]에서 arr[end]까지를 확인할 때  arr[start+1]에서 arr[end-1] 까지가

팰린드롬의 여부를 확인하므로 결과 값을 저장하는 DP방식으로 구현해야 반복 연산을 막을 수 있다.

 

bool dp[2001][2001]    //dp[start][end]가 팰린드롬인지의 여부를 저장

dp[start][end] = dp[start+1][end-1];

 

 

구현에 앞서 start==end인 경우 수열에 수가 단 한 개이기 때문에 항상 true임을 저장하고 시작하자.

 

for문을 순회할 때 1차 for문은 end값으로 하고, 2차 for문의 start의 값은 end미만까지로 제한해야 시작점(start)이 끝점(end)보다 커지는 경우를 제한할 수 있다.

 

arr[start]== arr[end]이고

end - start >=2인 경우 수열은 3개 이상의 수로 이루어져 있으므로 

dp[start][end] = dp[start+1][end-1];

로 계산된 값을 사용한다.

 

end - start >=2가 아니라면 수열은 두 개의 수만으로 

즉, arr[start]와 arr[end]만을 포함하므로 바로 true값을 저장해준다.

dp[start][end] = true;

 

코드