백준 10942번 팰린드롬?

🔒[문제 url]

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

🔑알고리즘

$S$번째 수부터 $E$번째 수가 팰린드롬을 이루기 위한 조건은 다음과 같다.
$S$번째 수와 $E$번째 수가 같고, $S+1$번째 수부터 $E-1$번째 수가 팰린드롬을 이룬다.

• dp[x][y] : $S=x$이고 $E=y$일 때 $S$번째 수부터 $E$번째 수가 팰린드롬이라면 1, 아니라면 0이다.
  • $S \leq E$이므로 $x>y$라면 무조건 0이고, $x=y$라면 무조건 1이다.
• seq[i]를 $i$번째 수라고 할 때, dp[x][y]가 1이기 위해서는
  seq[x] == seq[y] && dp[x+1][y-1] == 1이어야한다.
  • 양 끝이 같은 숫자이고 그 사이에 있는 수들이 팰린드롬을 이룬다면, 전체또한 팰린드롬임을 의미한다.
  • 또한, 이는 이차원 평면상에서 왼쪽아래 대각선이 1이여야함을 의미하므로,
    다음 순서로 dp를 갱신해나간다.
    $x+1=y$인 경우 양 끝 사이에 존재하는 수가 없으므로
    seq[x] == seq[y]라면 1이다.

🐾부분 코드

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> seq[i];
        dp[i][i] = 1;
    }
    cin >> m;
}

<입력 함수>
$S=E$인 구간의 dp 값을 1로 초기화한다.

for(int i = 1; i <= n - 1; i++)
    for(int j = 1; j + i <= n; j++)
    {
        if(i == 1 && seq[j] == seq[j + i])
            dp[j][j + i] = 1;
        else if(seq[j] == seq[j + i] && dp[j + 1][j + i - 1] == 1)
            dp[j][j + i] = 1;
        else dp[j][j + i] = 0;
    }

<dp 갱신>
$i$는 $S$와 $E$의 간격을 의미한다. 간격을 하나씩 넓혀가며 dp를 갱신한다.
i == 1이라면 $S+1=E$인 구간, 즉 길이가 2인 구간이므로 두 수가 같으면 1로 갱신한다.

🪄전체 코드

#include <iostream>
#include <string>
using namespace std;

int n,m;
int seq[2010];
int dp[2010][2010];

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> seq[i];
        dp[i][i] = 1;
    }
    cin >> m;
}


void SOLVE()
{
    for(int i = 1; i <= n - 1; i++)
        for(int j = 1; j + i <= n; j++)
        {
            if(i == 1 && seq[j] == seq[j + i])
                dp[j][j + i] = 1;
            else if(seq[j] == seq[j + i] && dp[j + 1][j + i - 1] == 1)
                dp[j][j + i] = 1;
            else dp[j][j + i] = 0;
        }

    for(int i = 0; i < m; i++)
    {
        int s,e; cin >> s >> e;
        cout << dp[s][e] << '\n';
    }
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기