링크

링크텍스트

문제

풀이

풀다가 막혀서 풀이를 봤다. 그래도 접근 방법은 비슷해서 쪼끔 뿌듯했다. DP세우는 건 비슷했지만 점화식을 세우는 부분에서 막혀서 참고했다 ㅜㅜ
DP[i][j]는 i는 시작점, j는 도착점이라고 생각하면 된다.
ABC라는 문자가 있으면
DP[1][1] = A
DP[1][2] = AB
이런식으로 생각하면 된다.
점화식을 유도하기 위해 쭉 풀어보면서 적었다.

내가 찾은 규칙을 보자면
1. i == j이면 글자 길이가 1이고 무조건 팰린드롬이다
2. j - i 가 1인경우 2글자인 경우는 2개의 문자만 비교해서 팰린드롬인지 체크하면 된다.
3. j - i 가 2인경우 3글자인 경우인데 이 경우는 첫번째와 마지막만 비교해서 팰린드롬인지 체크하면 된다.

1213121이라는 문자열을 예시로 들면
그리고 젤 중요한 점화식은 dp[1][5] = 12131인데 이 문자열의 앞뒤를 빼면 dp[2][4] = 213과 같다. 이게 점화식 세우는데 키포인트이다.
그러면 dp[1][5]를 만들려면 dp[2][4]를 체크하고 dp[2][4]가 팰린드롬이라면 dp[1][5]는 맨 앞자리와 맨 뒷자리만 체크하고 앞과 뒤가 같다면 팰린드롬이라고 처리해주면 된다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static int[][] dp;
	public static int[] arr;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		dp = new int[n][n];
		arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i=0;i<arr.length;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}	
		
		//차가 1 2 3인경우 셋팅
		for(int i=dp.length-1;i>=0;i--) {
			
			for(int j=0;j<dp[i].length;j++) {
			
				//글자가 1개면 팰린드롬
				if(i==j) dp[i][j] = 1;
				//글자가 2개인 경우 같으면 팰린드롬
				else if(j-i == 1) {
					if(arr[j] == arr[i]) dp[i][j] = 1;
				} // 글자가 3개인 경우 끝만 같으면 팰린드롬
				else if(j-i == 2) {
					if(arr[i] == arr[j]) dp[i][j] = 1;
				} else
				{
					
					//범위벗어나면 직접 계싼
					if(i+1 >= dp.length || j-1 < 0) {
						if(isPellindrom(i, j)) {
							dp[i][j] = 1;
						} 
					}else {
						if(dp[i+1][j-1] == 1 && arr[i] == arr[j]) dp[i][j] = 1;
					}
					
					
				}
			
			}
			
		}
		
		
		
		
		
//		for(int i=0;i<dp.length;i++) {
//			System.out.println(Arrays.toString(dp[i]));
//		}
		
		
		int testCase = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		for(int i=0;i<testCase;i++) {
			String[] element = br.readLine().split(" ");
			
			int start = Integer.parseInt(element[0]) - 1;
			int end = Integer.parseInt(element[1]) - 1;		
			sb.append(dp[start][end]).append("\n");
//			System.out.println(dp[start][end]);
		}
		
		System.out.println(sb.toString());
		
	}
	
	public static boolean isPellindrom(int startIdx, int endIdx) {
		for(int i=0;i<(endIdx - startIdx)/2;i++) {
			if(arr[startIdx+i] != arr[endIdx-i]) return false;
		}
		
		
		return true;
	}
	
}