백준 10942 c++ "팰린드롬?" -PlusUltraCode-

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

[필자 사고]

해당 문제는 동적프로그래밍을 이용하여 풀어야 되는 문제이다.

다만 필자는 해결법을 찾지 못해였다.

구글링을 통해 문제푸는 방식을 이해를 하였고 해다 사고 과정을 여기에 적겠다.

dp[][]를 2차원으로 정의했고 정의를 말해보자면 시작점과 끝점을 의미한다. dp[1][3] 이라고 한다면
첫번째 배열과 3번째 배열을 의미한ㄷ.

 

다음으로 하나의 글자는 반드시 펠린드롬이기 때문에 dp[1][1] ... 형태는 모두 1이라는 값으 넣어주었다.

그리고 추후 알고리즘을 구현하는데 있어서 2글자는 미리 사전에 설정해 주었따.

arr[i]==arr[i-1] 이 같다면 dp[i-1][i] =1 을 넣어주었다.

 

마지막 알고리즘은 바깥쪽 for 문은 길이를 의미하고

안쪽 for문은 처음 시작 인덱스를 의미한ㄷ.

그래서 if( arr[j]== arr[j+i] && dp[i+1][i+j-1] ==1) 인 경우 dp[i][i+j]  =1 값으로 갱신해주면 해결된다.

 

[코드 해설]

1. 입력 처리 (Input 함수)

Input() 함수는 수열의 크기 N과 원소들을 입력받고, 팰린드롬 여부를 저장할 DP 테이블 dp와 수열을 저장할 arr을 초기화한다.

• dp[i][j]: i부터 j까지의 구간이 팰린드롬이면 1, 아니면 0을 저장한다.
• arr[i]: i번째 원소를 저장하는 벡터.
• M: 질의의 개수를 입력받는다.

---

2. 팰린드롬 판별을 위한 DP 테이블 구성 (Game_Start 함수)

이 함수는 dp 테이블을 미리 계산하여 여러 개의 질의에 빠르게 답할 수 있도록 한다.

(1) 기저 사례 처리

• 길이가 1인 구간은 항상 팰린드롬이므로 dp[i][i] = 1로 설정한다.
• 길이가 2인 구간에서 두 값이 같다면 dp[i-1][i] = 1로 설정한다.

(2) 길이가 3 이상인 경우 DP 활용

• arr[j] == arr[i + j]이고 dp[j + 1][i + j - 1] == 1이면 dp[j][i + j] = 1로 설정한다.
• 즉, 양 끝의 값이 같고, 내부 부분이 팰린드롬이면 전체 구간도 팰린드롬이 된다.

---

3. 질의 처리

• M개의 질의를 입력받아 dp[s][e] 값을 출력하여 구간 [s, e]가 팰린드롬인지 판별한다.

[소스코드 ]

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

using namespace std;

vector<vector<int>> dp;
vector<int> arr;
int N, M;

void Input() {
	cin >> N;
	dp.assign(N + 1,vector<int>(N+1));
	arr.resize(N + 1);
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
	cin >> M;
}

void Game_Start() {
	for (int i = 1; i <= N; i++) {
		if (i != 1&& arr[i-1]==arr[i]) {
			dp[i-1][i] = 1;
		}
		dp[i][i] = 1;
		
	}

	for (int i = 2; i <= N - 1; i++) {
		for (int j = 1; j <= N; j++) {
			if (arr[j] == arr[i + j] && dp[j + 1][i + j - 1] == 1) {
				dp[j][i + j] = 1;
			}
		}
	}
	for (int i = 0; i < M; i++) {
		int s, e;
		cin >> s >> e;
		cout << dp[s][e] << '\n';
	}
}

int main(void) {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	Input();
	Game_Start();
}