백준 10942 : 팰린드롬?

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

10942번: 팰린드롬?

 

 

접근방법

---

이 문제는 DP를 사용하였습니다.

먼저 팰린드롬은 뒤집어도 같은 것을 말합니다.

 

이 문제에 DP를 적용하기 위해서는 다음과 같은 생각을 해야 합니다.

 

1 2 1 이라는 숫자열이 있습니다. 이 문자열은 팰린드롬입니다.

이 문자열에 앞 뒤로 같은 숫자인 2를 추가해 보면

2 1 2 1 2 처럼 팰린드롬이 됩니다.

 

즉, 팰린드롬에 같은 숫자를 앞뒤로 추가하면 팰린드롬이 되는 겁니다.

이를 이용해 보겠습니다.

 

	1	2	1
1	1	1, 2	1, 2, 1
2		2	2, 1
3			1

제일 왼쪽 열은 숫자열에서 시작하는 숫자, 제일 위쪽 행은 숫자열에서 끝나는 숫자를 의미합니다.

노란 숫자열을 보면 빨간 숫자열에 앞뒤로 1을 붙인 것을 알 수 있습니다.

 

정리하면 각 숫자열의 왼쪽 아래 칸이 숫자를 앞뒤로 붙이기 전이라는 것을 알 수 있습니다.

 

 

 

순서

---

1.  각 인덱스에서 숫자열이 팰린드롬인지 체크하는 2차원 DP 배열을 생성합니다.
2.  DP배열을 대각선으로 탐색합니다. (가장 왼쪽 대각선부터)
3.  첫 번째 대각선은 숫자가 하나이므로 항상 팰린드롬입니다.
4.  두 번째 대각선은 해당 행열이 의미하는 숫자가 같으면 팰린드롬입니다.(숫자열의 숫자가 2개밖에 없으므로)
5.  나머지 대각선들은 해당 행열이 의미하는 숫자가 같아야 하고 자신의 왼쪽 아래 칸이 팰린드롬이어야 팰린드롬입니다.

 

 

코드

---

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

public class baekjoon10942 {
	static int N, M;
	static int[] arr;
	static boolean[][] dp;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		arr = new int[N + 1];
		dp = new boolean[N + 1][N + 1];
		
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 1; j + i <= N; j++) {
				if(i == 0) {
					dp[j][j + i] = true;
				}
				else if(i == 1) {
					if(arr[j] == arr[j + i]) 
						dp[j][j + i] = true;
				}
				else {
					if(arr[j] == arr[j + i] && dp[j + 1][j + i - 1]) 
						dp[j][j + i] = true;
				}
			}
		}
		
		M = Integer.parseInt(br.readLine());
		for (int i = 1; i <= M; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			
			if(dp[s][e]) sb.append(1);
			else sb.append(0);
			sb.append('\n');
		}
		
		System.out.print(sb.toString());
	}
}

 

 

Reference

---

https://mygumi.tistory.com/176