[BOJ] 백준 10942 펠린드롬? - Python/Java

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

10942번: 팰린드롬?

 

해설

이 문제를 풀 때 가장 중요한 포인트는 두 가지라고 생각합니다.

 

1. 문제에서 주어진 각 숫자 자체는 팰린드롬 수가 아니어도 된다는 것

2. DP 메모이제이션의 순서를 고민해봐야 한다는 것

 

- 먼저 이 문제에서 팰린드롬인지를 확인할 때는 입력으로 주어진 개별 숫자가 팰린드롬인지의 여부는 관계가 없습니다. 즉, 입력이 123, 123 이렇게 두 수가 들어왔다고 하면, 123 / 123은 팰린드롬이 되는 것입니다. 저는 맨 처음에 각 입력의 숫자 역시 모두 팰린드롬 수가 되어야한다고 생각해서 훨씬 복잡하게 문제를 구현했고, 틀렸습니다 판정을 받았습니다.

 

- 두번째로 이 문제에서 고민해야 하는 부분은 DP의 메모이제이션 순서입니다. 이 문제에서 dp[i][j] = "i번째 수부터 j번째 수가 팰린드롬을 이루는가?" 라고 정의하면, dp[i][j]를 알기 위해서는 그 사이의 숫자가 팰린드롬인지를 판별해야 합니다.

 

즉, dp[i][j]가 팰린드롬이기 위해서는 dp[i+1][j-1]가 팰린드롬이면서 i번째와 j번째 수가 같아야하는 것이죠. 따라서, (i, j) 번째 DP값을 계산하기 위해서는 (i+1, j-1) 번째 DP값을 알아야한다는 뜻이 됩니다.

 

따라서, 아래 제 코드를 보시면 아시겠지만 DP 메모이제이션의 순서는 i를 끝점부터 감소시키면서 진행하고, j는 반대로 증가시키면서 진행합니다. 그래야 (i, j) 번째 DP값을 계산할 때, (i+1, j-1)번째 값을 참조할 수 있기 때문이죠. 이 부분은 학교 전공으로 '알고리즘 분석'을 들어서 DP의 메모이제이션 방향을 생각하는 데 도움이 된 것 같습니다.

 

 

풀이 - 파이썬

import sys
input = sys.stdin.readline

n = int(input())
number = [0] + list(map(int, input().split()))

# dp[i][j] = i~j번째 수를 선택했을 때 팰린드롬인가?
dp = [[False] * (n+1) for _ in range(n+1)]

# 자기 자신은 항상 팰린드롬
for i in range(1, n+1): dp[i][i] = True

# 연속된 두 수가 팰린드롬이려면 서로 같아야 함
for i in range(1, n):
    if number[i] == number[i+1]:
        dp[i][i+1] = True
    
# dp[i][j]를 결정하기 위해서는 dp[i-1][j+1]을 알아야한다.
# Memoization의 순서를 i는 내림차순, j는 오름차순으로 실행
for i in range(n-1, 0, -1):
    for j in range(i+1, n+1):
        if(dp[i+1][j-1] and number[i] == number[j]):
            dp[i][j] = True

for i in range(int(input())):
    s, e = map(int, input().split())
    isPalindrome = 1 if dp[s][e] else 0
    print(isPalindrome)

풀이 - 자바

package PS;

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

public class B_10942 {
    static String[] number;
    static boolean[][] dp;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        number =  br.readLine().split(" ");

        // dp[i][j] = i~j번째 수를 선택했을 때 팰린드롬인가?
        dp = new boolean[n+1][n+1];
        // 한 자리 숫자는 무조건 팰린드롬
        for(int i = 0; i <= n-1; i++) dp[i][i] = true;
        // 두 자리 숫자는 두 숫자만 관찰
        for(int i = 0; i < n-1; i++){
            if(number[i].equals(number[i+1])){
                dp[i][i+1] = true;
            }
        }

        // dp[i][j]를 결정하기 위해서는 dp[i-1][j+1]을 알아야한다.
        // Memoization의 순서를 i는 내림차순, j는 오름차순으로 실행
        for(int i = n - 1; i >= 0; i--){
            for(int j = i+1; j < n; j++){
                if(dp[i+1][j-1] && number[i].equals(number[j])){
                    dp[i][j] = true;
                }
            }
        }
        int m = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < m; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int isPalindrome = dp[s-1][e-1] ? 1 : 0;
            sb.append(isPalindrome).append('\n');
        }
        System.out.println(sb);
    }
}