[C++] 백준 10492: 팰린드롬?

 

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

 

문제 요약

수열이 주어졌을 때, S ~ E까지의 수열이 팰린드롬인지 확인하는 문제.

수열의 원소의 개수는 최대 2,000(10^3)개

질문의 횟수는 최대 1,000,000(10^6)개

 

※팰린드롬: 앞에서 읽어도 뒤에서 읽어도 같은 값을 나타내는 문자열.

 

 

풀이

1. 처음 생각했던건 단순 브루트포스였다.

 

하지만 시간 제한이 0.5초였고,

질문의 개수만 해도 10^6이라서 각 질문마다 팰린드롬인지 계산한다면

무조건 시간초과가 나올 수 밖에 없었다.

 

 

 

2. 다음으로 생각한 건 DP이다.

dp배열의 차원과 값을 설정하는 게 좀 시간이 걸렸다.

2차원으로 dp배열을 만들경우 모든 원소를 써야 되는 게 아닌가? 라는 고정관념에 빠져 더 힘들었던 거 같다.

 

결국, dp[i][j] = i ~ j 까지 팰린드롬을 이루고 있는 지의 여부

로 설정하고 문제를 풀어나갔다.

 

 

점화식이 생각이 안 날땐 역시 예제를 시뮬레이션 해보면 좋다.

예제 만세다.

1 2 1 3 1 2 1

 

 

1	2	1	3	1	2	1
1	0	1	0	0	0	1
	1	0	0	0	1	0
		1	0	1	0	0
			1	0	0	0
				1	0	1
					1	0
						1

 

색을 칠한 것에서 무슨 규칙이 보이는가???

시작점과 끝의 숫자가 같으면서, 왼쪽 아래가 1의 값을 가질 때 그 값은 1로 변한다.

 

 

즉, s와 e의 숫자가 같으며, s+1과 e-1의 수열이 팰린드롬을 이룰 때 s부터 e도 팰린드롬을 이루는 것이다!!

if(num[s] == num[e] && dp[s+1][e-1] == 1) dp[s][e] = 1;

Ex) 1 2 1 3 1 2 1의 예제에서

두 번째 2와 여섯 번째 2가 같고,

세 번째부터 다섯 번째까지의 수열이 팰린드롬(1 3 1)을 이루므로 2 1 3 1 2도 팰린드롬을 이루는 것을 볼 수 있다. 

 

 

 

이를 위해선 먼저 초깃값 설정을 해줘야한다.

1) 길이가 1일때, 모두 팰린드롬이므로 dp[i][i] = 1로 설정해준다.

2) 길이가 2일때, 위의 점화식은 길이가 3이상일때부터 성립하므로 체크해줘야 한다.

num[i] == num[i+1]일 때, dp[i][i+1] = 1로 설정해준다.

//초깃값 설정
    for(int i = 1; i <= n; i++){
        dp[i][i] = 1; //1개로 이루어진 수열
        if(num[i] == num[i+1]) dp[i][i+1] = 1; //2개로 이루어진 수열
    }

 

 

3) 길이가 3 이상일 때, 점화식을 통해 값을 구해준다.

//3개 이상으로 이루어진 수열 탐색
    for(int i = n-2; i >= 1; i--){ //시작점
        for(int j = 2; i + j <= n; j++){ //팰린드롬의 길이(-1)
            if(num[i] == num[i+j] && dp[i+1][i+j-1] == 1){
                dp[i][i+j] = 1;
            }
        }
    }

 

구현의 편리함을 위해 조금 변경을 했다.

for문의 두 변수를 '시작점'과 '팰린드롬의 길이 -1'로 설정하고 반복문을 짰다.

 

 

위와 같이 배열의 값은 아래부터 쭉쭉 채워져야 하므로

n-2부터 시작점을 시작해주었다는 게 주의할 점이다.

 

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int dp[2005][2005];
int num[2005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>num[i];
    }

    //초깃값 설정
    for(int i = 1; i <= n; i++){
        dp[i][i] = 1; //1개로 이루어진 수열
        if(num[i] == num[i+1]) dp[i][i+1] = 1; //2개로 이루어진 수열
    }

    //3개 이상으로 이루어진 수열 탐색
    for(int i = n-2; i >= 1; i--){ //시작점
        for(int j = 2; i + j <= n; j++){ //팰린드롬의 길이(-1)
            if(num[i] == num[i+j] && dp[i+1][i+j-1] == 1){
                dp[i][i+j] = 1;
            }
        }
    }

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

 

1. DP배열의 모든 값을 꼭 사용할 필요가 없다는 것

 

2. for문의 변수로 꼭 시작점과 끝점이 변수일 필요는 없다는 것(끝점 대신 길이를 사용)

을 배울 수 있었던 문제였다!!