문제 이해 단계
https://www.acmicpc.net/problem/10942
10942번: 팰린드롬?
총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.
www.acmicpc.net
팰린드롬은 좌우가 대칭되는 숫자로 이루어진 수열을 뜻한다.
예를 들어 (1,2,3,2,1), (1,3,1) (3) 등이 해당된다.
N개의 수열이 주어지고, 총 M개의 (S, E) 쌍이 들어온다.
이는 S번호부터 E번호까지로 이루어진 수열이 팰린드롬인지를 판단하는 것이다.
팰린드롬이면 1, 그렇지 않으면 0을 출력한다.
문제 접근 단계
일단 제한사항부터 살펴보자.
수열의 크기 N은 최대 2,000까지이다.
정수는 최대 100,000까지의 자연수이다.
질문의 개수는 최대 1,000,000개이다.
시간 복잡도 고려
팰린드롬이란 결국엔 데칼코마니(좌우대칭)를 의미한다.
팰린드롬을 구현할 때 일반적으로 스택을 사용한다.
짝수일 때는 수열을 절반으로 나누어 순서대로 스택에 담고
나머지 절반을 최신에 넣은 것부터 비교한다.
홀수일 때는 수열의 가장 가운데 수를 기준으로
왼쪽에 있는 값을 모두 순서대로 스택에 넣는다.
그리고 오른쪽에 있는 수열을 순서대로
스택에 가장 위에 있는 수부터 비교한다.
이런 방식으로 팰린드롬을 구현할 수 있다.
그런데 이 방식으로 구현하는 것에는 문제가 있다.
질문의 개수(M)가 최대 1,000,000개라는 것이다.
수열의 크기가 2,000일 때 1,000,000개의 질문을
모두 스택을 사용해서 팰린드롬을 판단한다면
10^6 * 10^3 = 10^9으로 제한시간인 0.25초가 훨씬 넘어버린다.
즉 스택으로 구현하면 안 되고 다른 방식을 사용해야 한다.
문제 유형 추측
0.25초를 넘지 않고 팰린드롬을 판단하려면 어떻게 해야 할까?
가장 먼저 생각나는 것은 한번 계산했던 결과를 저장해 두는 것이다.
특정 시작점(S)과 끝점(E)에서의 팰린드롬 계산 결과를 저장해 둔다.
이를 2차원 배열로 표현해 보겠다.
d [i][j] = -1 or 1
→ S = i이고 E = j 일 때의 팰린드롬의 결과는 -1 또는 1이다.
여기서 -1은 팰린드롬이 아니라는 것을 뜻하고,
1은 팰린드롬을 뜻한다.
이렇게만 하면 해결될까? 그렇지 않다.
M개의 입력이 모두 다를 수 있기 때문이다.
수열의 크기가 2,000개일 때 나올 수 있는 (S, E) 쌍의 경우의 수는
2000+1999+1998+…+1 ≥ 100,000
이기 때문에 또 시간초과가 뜬다.
결국에는 계산한 값을 이용해서 새로운 d배열을 구해야 한다.
이렇게 보니 이 문제는 DP 문제가 확실해 보인다.
DP 점화식 구하기
예제 입력을 예시로 들어보자.
d [1][7] 그러니까 (1,7) 일 때의 팰린드롬은 어떻게 판단해야 할까?
첫 번째는 일단 양 끝에 대칭되어 있는 원소가 서로 같아야 한다.
그러니까 d [1][7] 이니까 1번 원소와 7번 원소가 같아야 한다.
두 번째는 양끝을 제외한, 나머지 부분도 대칭을 이루어야 한다는 것이다.
여기서 이 표현을 다시 d 배열로 나타낼 수 있다.
애초에 d가 팰린드롬인지 아닌지를 나타내는 것이기 때문이다.
그러니까 d [1][7] 사이에 있는
d [2][6]이 팰린드롬이어야 한다.
정리해 보자면 d [1][7]이 팰린드롬이기 위한 조건은
1번 원소 == 7번 원소 && d [2][6] = 1
그렇기 때문에 우리는 d [2][6]이 팰린드롬인지 계산해야 한다.
d [2][6]을 계산하는 것도 d [1][7]을 계산하는 것과 똑같이 하면 된다.
![d[2][6]을 구하는 과정](https://blog.kakaocdn.net/dn/eaiDaL/btsts2C1B79/kkNkCWNwX9V6TBtOiU6vP0/img.png)
숫자만 다르지 똑같다.
d [3][5]를 구하기 위해 한번 더 한다.
![d[3][5]를 구하는 과정](https://blog.kakaocdn.net/dn/Ivls6/btstywJzj53/WF7zpvJiQcxg4gKdXI6veK/img.png)
여기서 d [4][4]는 굳이 계산할 필요 없다.
원소가 하나기 때문에 무조건 팰린드롬이기 때문이다.
위 과정에서 우리는 점화식을 이끌어낼 수 있다.
d [i][j] = d [i+1][j-1] && (arr [i] == arr [j])
근데 여기서 한 가지 주의해야 할 것은 원소의 개수가 짝수일 때이다.
예를 들어 d [3][4] 일 때를 생각해 보자.
그럼 해당 공식을 쓰면 d [4][3]이 되어버리기 때문에 성립하지 않는다.
그래서 j-i = 1 일 때의 예외처리를 잘해주는 것이 중요하다.
이제 점화식을 세웠으니 문제 구현 단계로 넘어가서 코드를 통해 설명하겠다.
문제 구현 단계
#include <iostream>
using namespace std;
int arr[2001] = {0,};
int dp[2001][2001] = {0,}; // 팰린드롬 배열 판단
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int N,M;
cin >> N;
for(int i = 1; i <= N; i++) {
cin >> arr[i];
dp[i][i] = 1; // 원소가 1개 인 것은 무조건 팰린드롬으로 초기화
}
// d 값을 넣어주기 위해서 역순으로 탐색
for(int i = N; i > 0; i--){
// i == j 일때는 필요없으므로 j = i+1부터 시작
for(int j = i+1; j <= N; j++){
// 양쪽 끝의 원소가 같을때
if(arr[i] == arr[j]){
// dp[3][4] 같은 경우
if(j-i == 1) dp[i][j] = 1; // 양쪽 끝 원소만 같다면 팰린드롬
else if(dp[i+1][j-1] == 1) dp[i][j] = 1; // 점화식
else dp[i][j] = -1; // 다 해당안되면 팰린드롬 아님
}
else dp[i][j] = -1; // 양쪽 끝의 원소가 다르면 팰린드롬 아님
}
}
cin >> M;
while(M--){
int S,E;
cin >> S >> E;
if(dp[S][E] == 1) cout << "1\n";
else cout << "0\n";
}
}dp 문제이기 때문에 코드는 그렇게 볼 것이 없다.
유심히 봐야 할 것은 S와 E가 같은 것을 무조건 팰린드롬으로 초기화해 주는 것.
그리고 j-i = 1 일 때는 양쪽 끝의 원소가 같은지만 판단해서
팰린드롬을 검사해 주는 예외를 추가해 주는 것이다.
나머지는 충분히 주석으로 이해할 수 있을 것이라고 생각하고 풀이를 마치겠다.
시행착오
처음에는 스택으로 풀었다가 시간초과가 난 다음에야 DP 문제인걸 깨달았다.
생각해 보니 스택으로 풀기에는 너무 쉽다 싶었다.
점화식은 직관적으로 생각하니까 쉽게 나왔다.
오히려 어렵게 생각하니까 더 안 나오더라
생활비..