문제

문제 링크

문제 접근

  • 이 문제를 어떻게 풀지 고민하다가 DP를 사용할 방법이 가까스로 떠올랐다.
  • 모든 값을 받은 후에 반복문으로 돌면서 각자를 기준점으로 삼아본다.
  • 기준점에서 뻗어나간게 가치있다면 ans[왼쪽][오른쪽]을 1로 바꿔주고 더 뻗어나간다.
  • 못뻗어나간다면 기준을 이동한다.
  • 여기서 같은 점에서 뻗어나갈 수도 있고 인접한 두점에서 뻗어나갈 수 있기 때문에 두 경우를 모두 진행해야한다.

코드

#include <cstdio>
int n, arr[2001], ans[2001][2001], m, v1, v2;
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++)scanf("%d", &arr[i]);
    for(int i = 0; i < n; i++){
        for(int j = 0; i - j >= 0 && i + j < n; j++){
            if(arr[i - j] != arr[i + j])break;
            ans[i - j][i + j] = 1;
        }
        for(int j = 0; i - j >= 0 && i + 1 + j < n; j++){
            if(arr[i - j] != arr[i + 1 + j])break;
            ans[i - j][i + 1 + j] = 1;
        }
    }
    scanf("%d", &m);
    while(m--){
        scanf("%d %d", &v1, &v2);
        printf("%d\n", ans[v1 - 1][v2 - 1]);
    }
}

느낀점

  • 디피는 어떻게 저장하면서 문제를 풀어나가면 연산량을 줄일 수 있을지 고민하면서 접근하면 좋을 것 같다.