백준 10942번 팰린드롬? (C++)

문제 링크 : https://www.acmicpc.net/problem/10942

10942번: 팰린드롬?

문제 요약

 

1. 팰린드롬(Palindrome)은 '회문'입니다. 예를들어 '스위스', '11011'처럼 뒤집어도 의미가 똑같은 단어를 뜻합니다.

2. 수열 n의 크기, 수열 n을 입력 받은 뒤, 테스트 케이스 m과 m개의 테스트 케이스를 입력받으세요. 

3. 각 테이트 케이스가 회문이면 1을, 그렇지 않을 경우 0을 출력하세요.

 

핵심 포인트

수열의 크기는 최대 2,000이며 테스트 케이스의 최대 크기는 1,000,000입니다.

무턱대고 for문을 남발하며 Brute Force를 활용하다가는 시간초과가 발생합니다. 때문에 DP로 주어진 수열의 특정 구간이 회문인지 아닌지를 판단하여 저장해야 합니다.

 

이 문제는 다음 3가지 로직을 활용하면 쉽게 풀 수 있습니다.

 

 

1. 길이가 1일 경우
   -> dp[i][i]는 무조건 true(회문)입니다.
2. 길이가 2일 경우
   -> v[i]==v[i+1]일 경우 dp[i][i+1]은 true입니다.
3. 길이가 3이상일 경우
   -> v[i]==v[j]이며, dp[i+1][j-1]이 true일 경우 dp[i][j]는 true입니다.
   
   * dp[i][j]의 뜻은 i번부터 j번까지가 회문인지 여부를 뜻합니다.

 

여기서 주의 사항은 3번입니다. v[i]==v[j]까지는 이해가 되지만 dp[i+1][j-1]이 true여야만 dp[i][j]가 true인지 이해가 안 갈 수 있습니다. 여기서 dp함수의 뜻을 잘 이해해야합니다. 만약 dp[1][5]가 주어지면, 이는 1번째 숫자부터 5번째 숫자가 회문인지 여부를 뜻합니다. 그리고 1번째 숫자부터 5번째 숫자가 회문이려면, 2번째 숫자부터 4번째 숫자까지가 회문이여야 공식이 성립됩니다.

 

 

문제 풀이

 

1. 변수를 선언하고 값을 입력받습니다.

    int n = 0, m = 0, temp = 0, st, ed;
    cin >> n;
    vector<int> v(n+1,0); // 수열
    vector<vector<bool>> dp(n+1,vector<bool>(n+1,false)); // i부터 j까지가 회문인지 여부
    for(int i=1; i<=n; i++) cin >> v[i];

.

2. 수열의 특정구간의 회문 여부를 판단합니다.

void palin(vector<vector<bool>> &dp, vector<int> &v, int n){
    for(int i=1; i<=n; i++){
        dp[i][i] = true; // 1. m의 길이가 1일 경우
    }
    for(int i=1; i<=n-1; i++){ //2. m의 길이가 2인 경우
        if(v[i]==v[i+1]) dp[i][i+1] = true;
    }
    for(int i=n-2; i>=1; i--){ // 3. m의 길이가 3 이상인 경우
        for(int j=i+2; j<=n; j++){
            if(v[i]==v[j]&&dp[i+1][j-1]) dp[i][j] = true;
        }
    }
}

... // int main()내부 
palin(dp,v,n);

여기서 주의 사항은 3번 입니다. 1~3번에 대한 설명은 핵심 포인트에서 언급이 되었으나, 3번의 경우 다른 두 케이스와는 다르게 i는 n-2부터 시작합니다. 즉, 앞이 아닌 끝부터 회문 여부를 판단합니다. 

 

이유는 다음과 같습니다. 만약 1는 1번부터, j는 i+2번부터 회문 여부를 판단한다면 다음과 같은 단계들을 거치게 됩니다. 

1 ~ 3 -> 2,2가 회문인지 판단
1 ~ 4 -> 2,3이 회문인지 판단
1 ~ 5 -> 2,4이 회문인지 판단

2,2와 2,3은 이미 구해뒀지만, 2,4는 구해둔 정답이 없습니다. 때문에 오답이 발생하므로, 앞이 아닌 끝부분부터 판단을 해야합니다.

 

3. 테스트 케이스를 입력받고 각 테스트 케이스에 대한 회문 여부를 출력합니다.

cin >> m;
    while(m--){
        cin >> st >> ed;
        cout << dp[st][ed] << "\n";
    }

 

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

using namespace std;

void palin(vector<vector<bool>> &dp, vector<int> &v, int n){
    for(int i=1; i<=n; i++){
        dp[i][i] = true; // m의 길이가 1일 경우
    }
    for(int i=1; i<=n-1; i++){ //m의 길이가 2인 경우
        if(v[i]==v[i+1]) dp[i][i+1] = true;
    }
    for(int i=n-2; i>=1; i--){ // m의 길이가 3 이상인 경우
        for(int j=i+2; j<=n; j++){
            if(v[i]==v[j]&&dp[i+1][j-1]) dp[i][j] = true;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n = 0, m = 0, temp = 0, st, ed;
    cin >> n;
    vector<int> v(n+1,0);
    vector<vector<bool>> dp(n+1,vector<bool>(n+1,false));
    for(int i=1; i<=n; i++) cin >> v[i];
    palin(dp,v,n);
    cin >> m;
    while(m--){
        cin >> st >> ed;
        cout << dp[st][ed] << "\n";
    }
    return 0;
}