[백준] 알고리즘 C++ 10942번 - 팰린드롬?문제

문제

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

10942번: 팰린드롬?

소스코드

/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
using namespace std;
int arr[2001];
int dp[2001][2001];

int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i];
    for(int i=1;i<=n;i++) dp[i][i]=1;
    for(int i=1;i<n;i++){
        if(arr[i]==arr[i+1]) dp[i][i+1]=1;
    }
    for(int i=2;i<n;i++){
        for(int j=1;j<=n-i;j++){
            if(arr[j]==arr[i+j]&&dp[j+1][i+j-1]==1){
                dp[j][j+i]=1;
            }
        }
    }
    int m;
    cin>>m;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        cout<<dp[x][y]<<"\n";
    }
}

해설

처음에 팰린드롬이 뭔지 이해가 가지 않았지만, 대충 예시의 문제를 보면 첫시작과 끝부분의 수는 같아야 한다는 것을 알 수 있다.

그리고 의미가 무엇인지 사전을 검색해보았다.

회문이라고한다. 거꾸로 읽어도 원래의 읽는 것과 같은 말을 뜻한다. 예시로 이동이같은 문자열을 말하는 것 같다.

모든 경우의 수를 다 계산해보는 것은 효율적이지 못하다.

우리는 효율적인 계산방법을 찾아봐야하는데, 큰 문제에서 작은 문제로 계속 분할 하여 문제를 해결 할 수 있는지 한번 알아봐야한다.

1 2 3 2 1

1 2 2 3 3 2 2 1

1 2 3 3 3 2 1

시작점과 끝지점이 같고 그 사이에 있는 수들이 팰린드롬 수라고 판단된다면, 전체 길이의 숫자는 팰린드롬 수라고 할 수 있다.

DP[i][j] = i번째 부터 시작하여 j로 끝나는 팰린드롬의 수 인지 아닌지 저장

시작점과 끝지점이 같은 수 = 모든 경우가 팰린드롬이라고 할 수 있다. 즉 시작점과 끝지점이 자기자신이면 당연히 팰린드롬이다. 즉 길이가 1인 경우 라고 볼 수 있겠죠?

 

길이가 2인 경우를 생각해보자, 이 경우의 팰린드롬은 시작점과 시작점+1이 같아야만 팰린드롬이 성립된다. 예를 들어

1 1

2 2

3 3 이런 숫자들만 성립된다.

 

우리는 머리로 바로 생각나는 팰린드롬을 복잡하게 점화식을 세워서 해줄필요 없이 답을 아는 부분은 바로 채워넣을 수 있다.

    for(int i=1;i<=n;i++) dp[i][i]=1;
    for(int i=1;i<n;i++){
        if(arr[i]==arr[i+1]) dp[i][i+1]=1;
    }

이 부분이 길이1과 2일 때의 팰린드롬의 수를 저장하는 것입니다. 

 

길이가 3이상인 경우부터는 시작점과 끝지점이 같아야하고 && 시작점+1과 끝지점-1이 팰린드롬의 수여야만 전체가 팰린드롬 수입니다.

dp[i][j]가 무엇을 뜻하는지 생각하고 for문을 작성해주면 됩니다.