HERSTORY

[C++ 알고리즘] 백준 10942번 : 팰린드롬?

  • 2021년 04월 07일


DP

팰린드롬?

풀이과정

1. 알고리즘 선택

문제를 보자마자 떠올렸던 풀이방법의 시간복잡도를 계산해보았다.

s,e를 입력받을 때 마다 s~e까지 검사하며 팰린드롬 여부를 확인하는 방법

이 방법은 1 ≤ N ≤ 2,000 이고, 1 ≤ M ≤ 1,000,000 이므로 최악의 경우 2,000* 1,000,000 = 2,000,000,000 (20억번)의 연산 횟수가 발생한다.

따라서 시간복잡도를 줄일 수 있는 방법이 필요했고, 일단 DP 같은데 조건을 어떻게 세워야할 지 몰라서 테스트케이스를 보면서 규칙을 찾았다.


2. 규칙 찾기

palindrom[s][e] = s~e 까지 수의 팰린드롬 여부

테스트케이스 1 2 1 3 1 2 1
palindrom [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

s ~ e까지가 팰린드롬이려면 s+1 ~ e-1 까지도 팰린드롬이어야 한다. 이 조건은 arr[s] == arr[e] && palindrom[s + 1][e - 1] == true로 표현할 수 있다.

따라서 palindrom[i][i]일때를 초기화 해주고,

for (int i = 1; i <= n; i++) {
	palindrom[i][i] = true;
}

(s, e)에서 palindrom[s + 1][e - 1]의 값에 접근하기 위해 반복문을 거꾸로 돌렸다.

for (int i = n - 1; i >= 1; i--) {
	for (int j = i + 1; j <= n; j++) {
	}
}


3. 예외 상황

2
1 1
1
1 2

코드를 작성했는데, 위의 테스트케이스일 때 오답을 출력해서 확인해보니, palindrom[i][i]일때 뿐만 아니라 palindrom[i][i+1] 또한 초기화해줘야함을 알았다.

for (int i = 1; i <= n - 1; i++) {
	if (arr[i] == arr[i + 1])
		palindrom[i][i + 1] = true;
}

를 추가하고

for (int i = n - 1; i >= 1; i--) {
	for (int j = i + 2; j <= n; j++) {
	}
}

로 반복문을 수정했다.


코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int arr[2001];
bool palindrom[2001][2001] = { false, };

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

	int n;
	cin >> n;

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

	for (int i = 1; i <= n - 1; i++) {
		if (arr[i] == arr[i + 1])
			palindrom[i][i + 1] = true;
	}

	for (int i = 1; i <= n; i++) {
		palindrom[i][i] = true;
	}

	for (int i = n - 1; i >= 1; i--) {
		for (int j = i + 2; j <= n; j++) {
			if (arr[i] == arr[j] && palindrom[i + 1][j - 1] == true) {
				palindrom[i][j] = true;
			}
		}
	}

	int m, s, e;
	cin >> m;

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

	return 0;
}



검색