[백준(Baekjoon)][자바(java)] 10942 : 팰린드롬? / 동적 계획법 2

 

www.acmicpc.net/problem/10942

10942번: 팰린드롬?

 

문제 풀이

 

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		int n = Integer.parseInt(  br.readLine() );
		int a[] = new int[n], i, j;
		StringTokenizer st = new StringTokenizer( br.readLine() );
		for( i = 0; i < n; i++ )
			a[i] = Integer.parseInt( st.nextToken() );
		int m = Integer.parseInt(  br.readLine() );
		int s[][] = new int[m][2]; // section -- s (start), e (end)
		for( i = 0; i < m; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 0; j < 2; j++ )
				s[i][j] = Integer.parseInt( st.nextToken() ) - 1;
		}
		br.close();
		
		boolean dp[][] = new boolean[n][n];
		int f, b, l, r;  // front, back, left, right
		for( f = 0; f < n; f++ ) {
			loop:
			for( b = n-1; b >= f; b-- ) {
				l = f; r = b;
				while( l <= r ) {
					if( a[l] == a[r] ) { l++; r--; }
					else continue loop;
				}
				dp[f][b] = true;
			}
		}
		
		StringBuilder sb = new StringBuilder();
		int res;
		for( i = 0; i < m; i++ ) {
			res = dp[s[i][0]][s[i][1]] ? 1 : 0;
			sb.append( res + "\n" );
		}

		System.out.println( sb.toString() );
	}
}

 

*  동적 계획법, 투 포인터

-  입력받을 시 m개의 질문 s와 e는 1씩 빼준다  ( 배열의 인덱스 0 부터 사용하기 위해 )
-  n*n 크기의 boolean dp[i][j] 배열 생성 후 팰린드롬의 i가 start일 때 j가 end일 경우 true 값을 넣는다
-  그 후 문제에서 입력받은 m개의 start & end 의 구간이 팰린드롬이면 ( if dp[s][e] == true ) 1, 아니면 0을 StringBuilder에 삽입하여 한꺼번에 출력