[BOJ21925] 짝수 팰린드롬 (동적 프로그래밍, DP)

 

 

---

문제링크

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

21925번: 짝수 팰린드롬

---

문제풀이

직접 풀이하여 통과는 하였지만, 방문 배열로 사용여부를 체크한다거나 맨앞에 펠린드롬이 아닌 경우 처리를 찾지 못해 아쉬움이 남는다.

 

- 동적 프로그래밍 풀이 

- palindrome 2차원 배열 전처리하여 구함 

팰린드롬인 경우
1) 자기 자신이거나 (길이1)
2) 바로 옆에 수와 같거나 (길이2)
3) 양 끝이 같고, (시작점 + 1) ~ (끝점 - 1) 범위의 수도 팰린드롬인 경우 

- 최대 수열의 길이 N = 5,000이기 때문에 int[][] palindrome 선언시 4byte * 5,000 * 5,000 = 100Mb 메모리를 차지 한다.

 

 

예제 입력1
10
1 1 5 6 7 7 6 5 5 5

예제 출력1
3

 

int[][] palindrome 전처리 결과

 

int[] dp 초기화

1	2	3	4	5	6	7	8	9	10
0	1	0	0	0	0	0	0	0	0

 

- 2중 for문 사용하여 짝수 자리, 그리고 짝수 범위에 대해 팰린드롬 여부 확인 

(1,4), (3,4)
(1,6), (3,6), (5, 6)
(1, 8), (3, 8), (5, 8), (7, 8)
(1, 10), (3, 10), (5, 10), (7, 10), (9, 10)

- 2중 for문에 증감연산자 += 2 하지 않을 경우 '시간 초과' 발생

- 팰린드롬인 경우 dp[j - 1] + 1한 값과 dp[i] 중 최대값으로 갱신

 

- boolean[] visited 숫자 사용여부 체크

마지막 dp[N]의 값이 0아니면 -1을 출력하면 될거라 생각했는데, 예제 입력3 확인시 문제가 되어 사용여부 체크하는 visited 배열 생성 

for(int i = 4; i <= N; i += 2) { // 짝수만 비교하면 됨 (log2(5000) 연산 횟수 줄어듬)
    for(int j = 1; j <= i; j += 2) {
        if(palindrome[j][i] == 1) {
            dp[i] = Math.max(dp[i], dp[j - 1] + 1);

            for(int k = j; k <= i; k++) visited[k] = true;
        }
    }
}

 

최종 int[] dp 결과 

1	2	3	4	5	6	7	8	9	10
0	1	0	0	0	1	0	2	0	3

- dp[6] = Math.max(dp[6], dp[5] + 1) 

- dp[8] = Math.max(dp[8], dp[2] + 1) // palindrome[3][8] 은 팰린드롬

- dp[10] = Math.max(dp[10], dp[8] + 1) 

 

 

*예외 케이스 확인

예외 입력
12
1 1 2 5 6 7 7 6 5 5 5 2

답 -1

 

참고. 그리디(탐욕) 알고리즘 풀이 

https://dev-ljw1126.tistory.com/392

[BOJ21925] 짝수 팰린드롬(그리디, 탐욕 알고리즘)

 

---

제출코드

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int N;
    
    static int[][] palindrome;

    static int[] data;
    
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        palindrome = new int[N + 1][N + 1];

        data = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N; i++) {
            data[i] = Integer.parseInt(st.nextToken());
        }

        pre(); // 팰린드롬 전처리

        // 초기화
        int[] dp = new int[N + 1];
        boolean[] visited = new boolean[N + 1];
        if(palindrome[1][2] == 1) {
            dp[2] = 1;
            visited[1] = true;
            visited[2] = true;
        }

        for(int i = 4; i <= N; i += 2) {
            for(int j = 1; j <= i; j += 2) {
                if(palindrome[j][i] == 1) { // 짝수 범위가 팰린드롬인지 확인
                    dp[i] = Math.max(dp[i], dp[j - 1] + 1);

                    for(int k = j; k <= i; k++) visited[k] = true;
                }
            }
        }

        // 결과
        boolean result = true;
        for(int i = 1; i <= N; i++) {
            if(!visited[i]) {
                result = false;
                break;
            }
        }

        if(result) {
            sb.append(dp[N]);
        } else {
            sb.append("-1");
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    // 팰린드롬 전처리 연산
    static void pre() {
        for(int i = 1; i <= N; i++) palindrome[i][i] = 1;

        for(int i = 1; i < N; i++) {
            if(data[i] == data[i + 1]) palindrome[i][i + 1] = 1;
        }

        for(int len = 3; len <= N; len++) { // 길이
            for(int i = 1; i <= (N - len + 1); i++) { 
                int j = i + len - 1;
                if(data[i] == data[j] && palindrome[i + 1][j - 1] == 1) {
                    palindrome[i][j] = 1;
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        input();
    }
    
}