Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

23. 동적 계획법2

조금 더 어려운 동적 계획법 문제를 풀어 봅시다.

Java / Python

4. 팰린드롬?

10942번

팰린드롬?

이번 문제는 자연수 N 개와 질문 M 개가 모두 주어질 때, 각 질문은 두 정수 S와 E로 S 번째 수부터 E 번째까지 수가 팰린드롬을 이루는지 물어보는 질문으로, 자연수가 팰린드롬인지 아닌지 답하는 문제입니다.

• Java

import java.io.*;
import java.util.*;

public class Main {

	static boolean[][] dp;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N + 1];
		dp = new boolean[N + 1][N + 1]; 
        
		StringTokenizer st = new StringTokenizer(br.readLine());         
		for (int i = 1; i <= N; i++) {  
			arr[i] = Integer.parseInt(st.nextToken());            
		}
		solve(N, arr);
		int M = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < M; i++){
			st = new StringTokenizer(br.readLine()); 
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());

			if(dp[start][end]) bw.write("1\n");
			else bw.write("0\n");  
		}

		bw.flush();
		bw.close();
		br.close();
	}
	public static void solve(int n, int[] arr) {
		for(int i = 1; i <= n; i++) dp[i][i] = true;
        
		for(int i = 1; i <= n - 1; i++)
			if(arr[i] == arr[i + 1]) dp[i][i + 1] = true;
        
		for(int i = 2; i < n; i++){
			for(int j = 1; j <= n - i; j++){
				if(arr[j] == arr[j + i] && dp[j + 1][j + i - 1]) 
					dp[j][j + i] = true;
			}
		}
	}
}

• Python

import sys
N = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
dp = [[0]*N for _ in range(N)]

for i in range(N):
    dp[i][i] = 1

for i in range(N - 1):
    if num[i] == num[i+1]:
        dp[i][i+1] = 1
    
for i in range(1, N):
    for j in range(2,i+1):
        if num[i] == num[i - j] and dp[i-j+1][i - 1] == 1:
            dp[i-j][i] = 1

for _ in range(M):
    S, E = map(int, sys.stdin.readline().split())
    print(dp[S - 1][E - 1])