[백준] 10942번 팰린드롬? [JAVA]

문제

 

 

 

 

---

풀이 방법

1. 필요 시 마다 검색
S, E가 주어진 후 S부터 E까지 팰린드롬인지 검사하는 방법의 경우

S = 1, E = N으로 주어지고 M = 100만인 경우, 2000*100만 = 연산 횟수가 20억이 된다.

1번 방법의 경우 이미 검색했던 정보를 저장하지 않아서 다시 검색하는 문제가 존재한다.

 

2. 가능한 모든 경우를 미리 검색해서 저장

미리 모든 경우에 대해 팰린드롬인지 검사를 해서 저장 해놓은 배열 ans[][]를 통해,

검색이 필요한 경우 ans[S][E]를 참조해 결과를 리턴하는 방식

S와 E를 위한 2중 for문과 S, E가 정해진 상황에서 팰린드롬인지 검사하기 위한 for문 총 3중 for문이 필요하고

연산 횟수는 2000*2000*2000 = 80억 이 된다.

 

3. 필요 시 마다 검색 && 이미 검색한 데이터는 재활용 (메모이제이션, DP)

1~10이 팰린드롬인지 확인하기 위해서는2~9가 팰린드롬인지 알아야 한다.    2~9가 팰린드롬인지 확인하기 위해서는    3~8가 팰린드롬인지 알아야 한다    .    .    .

 

결과적으로 1~10이 팰린드롬인지 검사를 한 적이 있다면2~9, 3~8, 4~7, 5~6이 팰린드롬인지도 검사를 한 적이 있게 된다.이 정보들을 저장하여 재귀로 호출하게 코드를 작성하였다.

---

코드 

package ps;

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

public class BOJ_10942 {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	
	static int N;
	static int[][] ans;
	static int[] arr;
	
	public static void input() throws Exception{
		N = Integer.parseInt(in.readLine());
		ans = new int[N][N];
		st = new StringTokenizer(in.readLine());
		arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
	}
	
	

	public static void main(String[] args) throws Exception {
		
		input();
		
		int M = Integer.parseInt(in.readLine());
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(in.readLine());
			int L = Integer.parseInt(st.nextToken());
			int R = Integer.parseInt(st.nextToken());
			
			int res = solve(L-1,R-1);
			if(res == 1)sb.append(res).append("\n");
			else sb.append(0).append("\n");
		}
		
		System.out.println(sb);

	}

	public static int solve(int L, int R) {
		
		// 기저
		if(L==R)return ans[L][R] = 1;
		if(L == R-1) {
			if(arr[L] ==arr[R])return ans[L][R] = 1;
			else return ans[L][R] = -1;
		}
		if(ans[L][R] != 0)return ans[L][R];
		
		// 유도
		if((solve(L+1,R-1) == 1) && (arr[L] == arr[R]) ) {
			return ans[L][R] = 1;
		}
		else {
			return ans[L][R] = -1;
		}
	}
}