[백준/C++] 10942번: 팰린드롬?

문제

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

---

문제 요약

자연수 N개가 주어졌을 때, M개의 질문에 대한 답을 출력한다.

 

각 질문마다 정수 S와 E가 주어지고, S번째 수부터 E번째까지 수가 팰린드롬을 이루는지 출력한다.

+ 팰린드롬이면 1, 아니면 0을 출력한다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

vector<int> sub_A, sub_B;

int n, m;

int arr[2020];

// dp[i][j]: arr[i:j]가 펠린드롬인지 여부
bool dp[2020][2020];

int main() {
    // 입출력 시간 단축
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // 칠판에 적은 자연수 입력
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    // 초기 설정
    for (int i = 1; i <= n; i++) {
        // 자기 자신은 펠린드롬
        dp[i][i] = true;

        // 이웃한 두 수가 같은 경우는 펠린드롬
        if (arr[i] == arr[i + 1]) {
            dp[i][i + 1] = true;
        }
    }

    // i는 범위 길이 - 1, j는 시작 인덱스
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= n; j++) {

            // 인덱스 범위를 벗어난 경우
            if (i + j > n) break;

            // dp 구하기
            if (dp[j + 1][j + i - 1] && arr[j] == arr[j + i]) {
                dp[j][j + i] = true;
            }
        }
    }

    cin >> m;

    // 질문
    while (m--) {
        int s, e;

        cin >> s >> e;

        if (dp[s][e]) cout << 1 << "\n";
        else cout << 0 << "\n";
    }

    return 0;
}

---

코드 설명

Bottom Up 다이나믹 프로그래밍을 이용한다.

 

dp[i][j]를 i번째 수부터 j번째 수까지가 펠린드롬인지 여부를 체크하는 배열로 정의한다.

 

dp[i][j]가 true이기 위해서는 두가지 조건이 필요하다.

 

1. dp[i + 1][j - 1]이 펠린드롬이다.

 

2. i번째 수와 j번째 수가 같다.

 

이를 Bottom Up 방식으로 접근하기 위해서 초기 dp값을 미리 설정해주어야 한다.

 

1. 원소 자기 자신 하나만 있을 때는 팰린드롬이다.

 

2. 이웃한 두 수가 같을 때는 팰린드롬이다.

(1번만 설정하면, 개수가 홀수일 때만 적용 가능하므로, 짝수일 때를 위해 설정한다.)

 

마지막으로 반복문을 접근할 때, i와 j를 그대로 정의할 수는 없다.

왜냐하면, dp[i + 1][j - 1]이 아직 구해지지 않았는데 접근이 되기 때문이다.

 

따라서, 범위 길이를 늘려가는 방식으로 이중 반복문을 사용한다.  

---

고찰

시간 초과가 발생해서 당황했지만, 입출력 수가 많기 때문에 입출력 단축 코드를 사용해서 해결했다.

 

ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);