[개쉬운 풀이] 백준 10942 팰린드롬?

문제

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그다음, 명우에게 질문을 총 M번 한다.

각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니 다를 말해야 한다.

예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.

• S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
• S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
• S = 3, E = 3인 경우 1은 팰린드롬이다.
• S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.

자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

 

팰린드롬

거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열이다.

 

생각

문자열을 보고 어느 구간에서 팰린드롬이 나타나는지 구하는 문제이다. 문제에 테스트케이스가 있고 시간제한이 있으므로 해당문제는 DP로 해결해야한다고 생각했다. 따라서 최장길이수열과 비슷하게 문제를 접근하였다.

 

주어진 자연수 N개를 vector에 1~N까지 저장을 하고 이를 dp를 이용해 dp[a][b]는 a~b까지의 구간은 팰린드롬인지를 나타낼 것이다.

 

1. 길이가 1일때, (자기 자신 (r == c)) 해당 dp값은 무조건 1이다.

2. 길이가 2일때, 두 숫자의 번호가 같은지 확인한다.

3. 길이가 3이상일 때, 붉은색 선의 방향을 따라 탐색한다. 왜냐하면 첫 숫자를 기준으로 1~N까지의 모든 숫자를 탐색하게 되었을 때 그 사이에 생기는 팰린드롬은 다음 숫자를 기준으로 탐색을 할 때 계산을 통해 나타낼 수 있기 때문이다.

- ex) [1 ~ 7]구간의 팰린드롬을 확인하는 방법은 [2~6] 구간의 팰린드롬을 확인하고 [1]과 [7]이 같은 숫자임을 증명하면 됨.

따라서, 우리는 현재 구간 크기 j를 기준으로 각 번호 i를 j구간만큼 팰린드롬을 모두 확인하고 j의 크기를 늘려서 전체 탐색을 한다.

 

a. 빨간색을 보면 현재 [1]과 [5]는 같은 숫자이지만, [2~4] 구간이 팰린드롬이 아니므로 (dp [2][4] == 0) dp [1][5]가 0 임을 알 수 있다.

b. 초록색을 보면 현재 [2]와 [6]은 같은 숫자이지만, [3~5] 구간이 팰린드롬이므로 (dp [3][5] == 1) dp [2][6]이 1 임을 알 수 있다.

c. 해당 위치 dp [i][i+j]를 알기 위해서는 dp [i+1][i+j-1]을 알아야 하므로 빨간색 화살표 방향으로 탐색을 진행하는 것이다.

 

코드

struct T{
    int s,e;
};
int n;
vector<int> number;
int m;
vector<T> question;
bool dp[2001][2001];

void input(){
    cin >> n;
    number.resize(n+1,0);
    //인덱스가 편하기 위해서 1부터 N까지의 인덱스로 저장함
    for(int i = 1; i <= n; i++){
        cin >> number[i];
    }
    cin >> m;
    //테스트케이스를 담아둠
    for(int i = 0; i < m; i++){
        T tmp;
        cin >> tmp.s>> tmp.e;
        question.push_back(tmp);
    }
}

input() 이다.

 

void palindrome(){
    memset(dp,false,sizeof(dp));
    
    for(int i = 1; i <= n; i++){
        dp[i][i] = true; //1번 조건) 길이가 1일 때
        if(i != 1 && number[i] == number[i-1]) dp[i-1][i] = true; //2번 조건) 길이가 2일 때
    }
    
    //길이가 3이상일 때
    //j크기를 고정시키고 이 크기에 해당하는 구간을 모두 탐색함 (빨간색 화살표 방향으로 탐색하기 위함)
    for(int j = 2; j <= n-1 ; j++){
        for(int i = 1; i+j <= n; i++){
        	//같은 숫자인가?
            if(number[i] == number[i+j]){
            	//사이 구간들이 팰린드롬을 이루는가?
                if(dp[i+1][i+j-1] == 1){
                    dp[i][i+j] = true;
                }
            }
        }
    }
}

dp를 작성할 때 보통은 좌에서 우방향으로 탐색을 하였지만, 해당 문제에서는 사선방향으로 탐색을 해서 dp에 저장해야하는 문제이다. 
이 방법을 유용하게 생각할 줄 알아야한다.

 

전체 코드

#include <iostream>
#include <vector>
#include <memory.h>
#define endl '\n'
using namespace std;

struct T{
    int s,e;
};
int n;
vector<int> number;
int m;
vector<T> question;
bool dp[2001][2001];

void input(){
    cin >> n;
    number.resize(n+1,0);
    for(int i = 1; i <= n; i++){
        cin >> number[i];
    }
    cin >> m;
    for(int i = 0; i < m; i++){
        T tmp;
        cin >> tmp.s>> tmp.e;
        question.push_back(tmp);
    }
}

void palindrome(){
    memset(dp,false,sizeof(dp));
    for(int i = 1; i <= n; i++){
        dp[i][i] = true;
        if(i != 1 && number[i] == number[i-1]) dp[i-1][i] = true;
    }
    for(int j = 2; j <= n-1 ; j++){
        for(int i = 1; i+j <= n; i++){
            if(number[i] == number[i+j]){
                if(dp[i+1][i+j-1] == 1){
                    dp[i][i+j] = true;
                }
            }
        }
    }
}

void sol(){
    for(int i = 0; i < question.size(); i++){
        int s = question[i].s;
        int e = question[i].e;
        cout << dp[s][e] << endl;
    }
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    input();
    palindrome();
    sol();
    return 0;
}

테스트 케이스가 들어가 있어서 입출력이 많은 문제이다.

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

#define endl '\n'

을 통해서 입출력 시간을 줄여주었다. 이를 사용할 때는 cin cout만 사용해야한다.