[동적계획법] C11 백준 10942 팰린드롬? 풀이

문제

• 10942

풀이 과정

• 먼저 실패한 코드

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    
    int arr[n];
    for (int i=0; i<n; i++) {
        scanf("%d", &arr[i]);
    }
    
    int m;
    scanf("%d", &m);
    for (int i=0; i<m; i++) {
        int x,y;
        scanf("%d %d", &x, &y);
        x--;
        y--;
        
        int flag = 0;
        while (x < y) {
            if (arr[x] != arr[y]) {
                flag = 1;
                break;
            }
            x++;
            y--;
        }
        if (flag) {
            printf("0\n");
        } else {
            printf("1\n");
        }
    }
    
    return 0;
}

• 1s로 보고 M이 1,000,000 이길래 음 그냥 돌리면 되겠는데? 하고 돌렸는데 시간초과 났다
• 뭘로 풀어야 할까.. 스택? 도 아니고 범위 지정 해야 하니까
• 결국에 범위가 가변이고 배열은 정해져 있으니 뭔가 DP같은데... 식이 떠오르지 않는다
  • dp[1]일때 뭘 넣어야 한다는거지? 이렇게 생각하다가 그냥 정답코드 확인했다
• DP 테이블
  • dp[i][j] 일 때 i번째부터 j번째까지의 수열이 팰린드롬인지 판단 여부를 넣음
  • dp[i][i] = 1, 길이가 1인 부분 수열은 항상 팰린드롬
  • dp[i][i+1] = 1 or 0, 길이가 2인 부분 수열은 arr[i] == arr[i+1] 이 같으면 팰린드롬 1, 아니면 0
  • 길이가 3이상인 부분수열에 대해 점화식
    • arr[i] == arr[j] 일 경우, dp[i+1][j-1] = 1

정답 코드

#include <stdio.h>

#define MAX 2000

int main() {
    int n;
    scanf("%d", &n);
    
    int arr[n];
    for (int i=0; i<n; i++) {
        scanf("%d", &arr[i]);
    }
    
    int dp[MAX][MAX] = {0,};
    for (int i=0; i<n; i++) {
        dp[i][i] = 1;
        if (i<n-1 && arr[i] == arr[i+1]) {
            dp[i][i+1] = 1;
        }
    }
    
	// i는 부분 수열의 길이
	// j는 부분 수열의 시작 인덱스
    // k는 부분 수열의 끝 인덱스
    for (int i=3; i<=n; i++) {
        for (int j=0; j<=n-i; j++) {
            int k = j+i-1;
            if (arr[j] == arr[k] && dp[j+1][k-1] == 1) {
                dp[j][k] =1;
            }
        }
    }
    
    int m;
    scanf("%d", &m);
    for (int i=0; i<m; i++) {
        int x,y;
        scanf("%d %d", &x, &y);
        x--;
        y--;
        
        printf("%d\n", dp[x][y]);
    }
    
    return 0;
}