[백준 10942번] 팰린드롬? || [백준 1509번] 팰린드롬 분할

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

 

package dp;

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

public class DP10942 {
    static int N, M;

    static int[] exList;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        exList = new int[N];

        for (int i = 0; i < N; i++) {
            exList[i] = Integer.parseInt(st.nextToken());
        }

        M = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        boolean[][] dp = new boolean[N][N];

        // 길이가 1이거나
        for (int one = 0; one < N; one++) {
            dp[one][one] = true;
        }


        //  길이가 2인데 2개 값이 같을떄
        for (int two = 0; two < N - 1; two++) {
            if (exList[two] == exList[two + 1]) {
                dp[two][two + 1] = true;
            }
        }


        for (int len = 3; len < N + 1; len++) {

            for (int sIdx = 0; sIdx < N - len + 1; sIdx++) {

                int eIdx = sIdx + len - 1;

                dp[sIdx][eIdx] = (exList[sIdx] == exList[eIdx]) && dp[sIdx + 1][eIdx - 1];

            }
        }


        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int startIdx = Integer.parseInt(st.nextToken()) - 1;
            int endIdx = Integer.parseInt(st.nextToken()) - 1;

            if (dp[startIdx][endIdx]) sb.append("1\n");
            else sb.append("0\n");


        }

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

    }
}

 

 

이 문제 와인문제랑 많이 비슷하다. 

 

핵심은 sb 출력 한곳에 모아서 해줘야된다. 아니면 터짐..! 

 

이 문제의 하위호환

https://balhae.tistory.com/123

[백준] 1213번

 

 

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

 

package dp;

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

public class DP1509 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String input = br.readLine();
        int size = input.length();
        boolean[][] dp = new boolean[size][size];

        for (int one = 0; one < size; one++) {
            dp[one][one] = true;
        }

        for (int two = 0; two < size - 1; two++) {
            if (input.charAt(two) == input.charAt(two + 1)) {
                dp[two][two + 1] = true;
            }
        }

        for (int len = 3; len < size + 1; len++) {
            for (int s_idx = 0; s_idx < size - len + 1; s_idx++) {
                int e_idx = s_idx + len - 1;
                dp[s_idx][e_idx] = input.charAt(s_idx) == input.charAt(e_idx) && dp[s_idx + 1][e_idx - 1];
            }
        }

        simulation(dp, size);

    }

    private static void simulation(boolean[][] dp, int size) {
        int[] result = new int[size];
        for (int e_idx = 0; e_idx < size; e_idx++) {

            result[e_idx] = Integer.MAX_VALUE;
            for (int s_idx = 0; s_idx <= e_idx; s_idx++) {
                if (dp[s_idx][e_idx]) {
                    if (s_idx == 0) {
                        result[e_idx] = 1;
                    } else {
                        result[e_idx] = Math.min(result[e_idx], result[s_idx-1] + 1);
                    }
                }
            }

            System.out.println(result[size - 1]);
        }
    }
}

 

앞에 문제에 확장 버전이다. 분할을 이용해서 잘 생각을 해야된다. 

만약 AABCBB가 있을떄 BB를 탐색할때 이 둘을 하나로 묶고 +1로 생각을 해야된다.