[BOJ]10942_팰린드롬_Java

--문제--

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

10942번: 팰린드롬?

--문제 접근--

팰린드롬의 정의:회문 또는 팰린드롬은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열 등이

팰린드롬은 로꾸거 인걸로 이해하고 문제를 풀어봤습니다.

맨 처음은 1차원적으로 S와 E가 주어질 때 첫 번째 항과 마지막항과 비교해가면서 같지 않을 때는 팰린드롬이 되지 않는다고 판단하고 문제를 풀어봤을 때 바로 풀어졌지만 이문제의 의도는 아닌 거 같아 조금 더 생각을 해봤습니다.

생각을 하다가 풀지 못하여 검색을 하면서 아이디어를 유추했습니다.

12321 일 때 1 5가 팰린드롬이 되어야 한다면 2 4 도 팰린드롬이 차례대로 다되어야 한다는 점에서 착안하였습니다.

그래서 생각한 점화식이

for(int i=2;i<=N;i++) {
			for(int j=1;i+j<=N;j++) {
				if(arr[j]==arr[i+j]&&dy[j+1][i+j-1])dy[j][i+j]=true;
			}
		}

입니다.

기본적인 흐름은 

i가 2일 때 길이는 3이므로

1 2 3 2 1

1 2 3 2 1 

1 2 3 2 1

i가 3이고 길이가 4일 때

1 2 3 2 1

1 2 3 2 1 

이렇게 검사를 차근차근해가면서 답을 구해가는 형식입니다.

`

package Class5;

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

public class BOJ_10942_팰린드롬 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(br.readLine());
		StringTokenizer st=null;
		st=new StringTokenizer(br.readLine());
		int[] arr=new int[N+1];
		for(int i=1;i<=N;i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		int TC=Integer.parseInt(br.readLine());
		StringBuilder sb=new StringBuilder();
		for(int t=0;t<TC;t++) {
			st=new StringTokenizer(br.readLine());
			int start=Integer.parseInt(st.nextToken());
			int end=Integer.parseInt(st.nextToken());
			int ans=1;
			while(start<end) {
				if(arr[start]!=arr[end]) {
					ans=0;
					break;
				}
				start++;
				end--;
			}
			sb.append(ans+"\n");
		}
		System.out.println(sb);
	}
}

 

다이나믹

package Class5;

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

public class BOJ_10942_팰린드롬 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(br.readLine());
		StringTokenizer st=null;
		st=new StringTokenizer(br.readLine());
		int[] arr=new int[N+1];
		for(int i=1;i<=N;i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		boolean[][] dy=new boolean[N+1][N+1];
		for(int i=1;i<=N;i++) {
			dy[i][i]=true;
		}
		for(int i=1;i<N;i++) {
			if(arr[i]==arr[i+1])dy[i][i+1]=true;
		}
		for(int i=2;i<=N;i++) {
			for(int j=1;i+j<=N;j++) {
				if(arr[j]==arr[i+j]&&dy[j+1][i+j-1])dy[j][i+j]=true;
			}
		}
		int TC=Integer.parseInt(br.readLine());
		StringBuilder sb=new StringBuilder();
		for(int t=0;t<TC;t++) {
			st=new StringTokenizer(br.readLine());
			int start=Integer.parseInt(st.nextToken());
			int end=Integer.parseInt(st.nextToken());
			if(dy[start][end])sb.append(1+"\n");
			else sb.append(0+"\n");
		}
		System.out.println(sb);
	}
}