[백준 10942번 C/C++] 팰린드롬?

 

[백준 10942번 C/C++] 팰린드롬? 

 

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

10942번: 팰린드롬?

---

 

해결전략

 

동적계획법 Dynamic Programming (DP)

메모이제이션 Memoization

---

 

시도한 코드 - 시간초과

 

처음 시도한 코드

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

int n, m;
vector<int> v;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	v.resize(n+1);
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
	}
	cin >> m;
	int s, e;
	for (int i = 0; i < m; i++) {
		cin >> s >> e;

		int p1 = s, p2 = e;
		bool palindrome = true;
		while (p1 < p2)
		{
			if (v[p1] == v[p2]) {
				p1++;
				p2--;
			}
			else {
				palindrome = false;
				break;
			}
		}

		if (palindrome) cout << "1" << "\n";
		else cout << "0" << "\n";
	}

	return 0;
}

 

두번째 시도한 코드

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

int n, m;
vector<int> v;
vector<vector<bool>> dp;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	v.resize(n + 1);
	dp.resize(n + 1, vector<bool>(n + 1));
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
	}

	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			if (i == j) {
				dp[i][j] = true;
				continue;
			}

			int p1 = i, p2 = j;
			dp[i][j] = true;
			while (p1 < p2)
			{
				if (v[p1] == v[p2]) {
					p1++;
					p2--;
				}
				else {
					dp[i][j] = false;
					break;
				}
			}
		}
	}

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

	return 0;
}

 

 

처음에 DP인지 모르고 풀어서 올바른 접근을 하기까지 오래 걸렸다.

 

---

 

정답 코드

 

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

int n, m; // n: 숫자 배열의 크기, m: 질의의 수
vector<int> v;
vector<vector<bool>> dp; // 팰린드롬 여부를 저장할 2차원 벡터

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	v.resize(n + 1);
	dp.resize(n + 1, vector<bool>(n + 1, false));
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
	}

	// 길이가 1인 경우, 모든 숫자는 자기 자신만으로 팰린드롬
	for (int i = 1; i <= n; i++) {
		dp[i][i] = true;
	}

	// 길이가 2인 경우, 연속된 두 숫자가 같으면 팰린드롬
	for (int i = 1; i < n; i++) {
		if (v[i] == v[i + 1]) {
			dp[i][i + 1] = true;
		}
	}

	// 길이가 3 이상인 경우 
	for (int i = n - 1; i >= 1; i--) { // 뒤에서부터 시작하여 앞으로 이동하며
        for (int j = i + 2; j <= n; j++) // i에서 2 더한 위치부터 시작하여 배열의 끝까지
        {
            // 시작 인덱스의 값과 끝 인덱스의 값이 같고, 그 사이 배열이 팰린드롬이면
            if (v[i] == v[j] && dp[i + 1][j - 1] == true) {
                dp[i][j] = true; // 해당 범위도 팰린드롬으로 설정
            }
        }
    }

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

	return 0;
}

 

 

테스트 케이스

1

2

1

3

1

2

1

dp[][]	1	2	3	4	5	6	7
1	O	X	O	X	X	X	O
2		O	X	X	X	O	X
3			O	X	O	X	X
4				O	X	X	X
5					O	X	O
6						O	X
7							O

 

 

길이가 3 이상일 경우, v[ i ] == v[ j ] 이고  dp[ i + 1 ][ j - 1 ] = true 라면 팰린드롬

•  ex. s = 2, e = 6 인 경우,
  v[ 2 ] == v[ 6 ] 이고, dp[ 3 ][ 5 ] = true 이라면 (=주어진 배열의 3 ~ 5사이 수는 팰린드롬이다)
  v 배열의 2~6사이의 수도 팰린드롬이고, dp[ 2 ][ 6 ] = true 라고 표현할 수 있다. 

 

 

 

 for (int i = n - 1; i >= 1; i--) { // 뒤에서부터 시작하여 앞으로 이동하며
    for (int j = i + 2; j <= n; j++) // i에서 2 더한 위치부터 시작하여 배열의 끝까지
    { 
        // 시작 인덱스의 값과 끝 인덱스의 값이 같고, 그 사이 배열이 팰린드롬이면
        if (v[i] == v[j] && dp[i + 1][j - 1] == true) {
            dp[i][j] = true; // 해당 범위도 팰린드롬으로 설정
        }
    }
}

 

 

for (int len = 3; len <= n; len++) { // len: 부분 문자열의 길이를 3부터 n까지 증가
    for (int i = 1; i <= n - len + 1; i++) { // 시작 인덱스 i를 설정 // n - len + 1: 부분 문자열이 전체 문자열의 끝에 도달하기 바로 직전의 시작점
        int j = i + len - 1; // 끝 인덱스 j를 계산
        // 시작과 끝 문자가 같고, 내부 문자열이 팰린드롬이면
        // v[i] == v[j]: 부분 문자열의 시작과 끝 문자가 같아야 한다.
        // dp[i + 1][j - 1]: 시작과 끝 문자를 제외한 내부 부분 문자열이 이미 팰린드롬인지 확인.
        if (v[i] == v[j] && dp[i + 1][j - 1]) {
            dp[i][j] = true; // 인덱스 i에서 j까지의 부분 문자열은 팰린드롬
        }
    }
}

 

 

 

 

---