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

10942. 팰린드롬

10942번: 팰린드롬?

 

---

 

문제 풀 때 막혔던 것 (바보짓..)

초장부터 문제를 잘못 이해해서 초반에 엄청난 시간을 썼다...

 

 

나는 처음에, 숫자를 받으면 하나의 문자열로 생각했다.

 

반대로,

이렇게 하나의 문자열로 생각하지 말고 숫자 자릿수에 상관없이 하나 하나 비교해야 하는 것이었다!

 

---

여기까지는 괜찮았지만, 팰린드롬을 비교할 때 치명적인 실수를 했다.

 

p1(index)부터 p2(index)까지의 수가 팰린드롬인지 확인할 예정이었다. 따라서 p1부터 증가하는 값과 p2부터 감소하는 값을 비교해줄 생각이었는데...

for (int i = p1; i < (p2 - p1) / 2 + 1; i++)
{
	// i와 p2-(i-p1) 비교
}

for문의 조건식처럼 p1부터 (p2-p1)까지 돌려준 것이다! (p2-p1)은 돌아가는 횟수이지, 조건이 아니잖아 ㅠ_ㅠ 이것때문에 몇 시간은 고생한 것 같다...

 

for (int i = p1; i < p1 + (p2 - p1) / 2 + 1; i++)
{
	// i와 p2-(i-p1) 비교
}

조건식에 p1을 더해주는 것으로 끝을 냈다. 이런 작지만, 치명적인 실수를 하지 않도록 조심해야겠다... 오랜만이라서 그런가. 항상 주의하기!!

 

---

 

알고리즘 설계

 

수열의 크기는 2000, S부터 E까지가 팰린드롬인지 구해야 하는데... 질문의 개수가 무려 1,000,000이기 때문에 백만 번을 팰린드롬인지 아닌지 판별하기는 시간이 초과가 날 게 분명했다.

 

그래서 무작정 DP를 이용해보기로 했다. N부터 M까지가 회문인지 아닌지 판별하는 데이터값을 2차원 배열로 저장했다. DP를 이용해 그 데이터값을 활용해 팰린드롬인지 아닌지 판별할 수 있게 했다.

 

이렇게 저장했다!

 

0 => 팰린드롬이 아님
1 => 모든 수가 연속인 팰린드롬 (11111)
2 => 1이 아닌 팰린드롬 (12121)

1과 2를 나눈 이유는 DP[i-1][j]나 DP[i][j-1]이 2인 경우에는 DP[i][j]= 0임을 판별해주기 위해서이다. 

그림으로 설명하자면,

 

1의 경우는 팰린드롬임을 판별할 필요 없이, 끝자리와 첫자리가 같다면 팰린드롬 처리를 해주었다.

2의 경우는 첫자리와 끝자리가 같아도, 양 옆에 들어가면 팰린드롬이 아니므로! 팰린드롬임을 판별하지 않고 팰린드롬이 아님을 체크해주었다.

 

---

 

 

N번째부터 M번재까지의 수열을 팰린드롬인지 판별한다.

• N부터 N까지는 한 자리이므로 무조건 팰린드롬 처리해준다.

for(int i = 0; i < N; i++)
	dp[i][i] = 1;

• i부터 i+1~N(j)까지가 팰린드롬인지 판별해준다.
  • 이때, 수열의 첫째 숫자와 마지막 숫자가 같을 때만 판별해준다. 첫번째부터 마지막 숫자와 다르면 일단 회문이 아니기 때문에! 
    • dp[i][j-1]이나 dp[i-1][j]가 1(모든 수가 같은 팰린드롬)이면 dp[i][j] = 1
    • dp[i][j-1]이나 dp[i-1][j]가 2(모든 수가 같지 않은 팰린드롬)이면 dp[i][j] = 0
    • 그렇지 않다면 팰린드롬 함수를 호출해 판별한 값을 넣어준다.

 

 

코드

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

// i부터 j까지가 팰린드롬인지 아닌지를 판별
// 0 => 팰린드롬 X
// 1 => 모든 수가 같은 팰린드롬
// 2 => 1이 아닌 팰린드롬
int dp[2001][2001];
vector<int> seperated;

// p1(index)~p2(index) 가 팰린드롬인지 확인하기
bool IsPalindrome(int p1, int p2)
{
	for (int i = p1; i < p1 + (p2 - p1) / 2 + 1; i++)
	{
		if (seperated[i] != seperated[p2 - (i - p1)])
		{
			return false;
		}
	}
	return true;
}

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

	int n, a, b;
	int input;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> input;
		seperated.push_back(input);
	}

	// DP
	for (int i = 1; i <= n; i++)
	{
		dp[i][i] = 1;

		for (int j = i + 1; j <= n; j++)
		{
			if (seperated[i - 1] == seperated[j - 1])
			{
				// 연속된 수이면 팰린드롬
				if (dp[i][j - 1] == 1 || dp[i - 1][j] == 1)
				{
					dp[i][j] = 1;
				}
				// 바로 전에 연속된 수가 아닌 팰린드롬일 때는 팰린드롬이 아님
				else if (dp[i][j - 1] == 2 || dp[i - 1][j] == 2)
				{
					dp[i][j] = 0;
				}
				// 그렇지 않다면 판별
				else if (IsPalindrome(i - 1, j - 1))
				{
					dp[i][j] = 2;
				}
			}
		}
	}

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> a >> b;
		cout << (bool)dp[a][b] << '\n';
	}
}

 

N부터 M까지가 팰린드롬인지 2차원 배열에 저장해준 아이디어를 생각해 뿌듯했다 ㅎ_ㅎ 팰린드롬일 때 1과 2를 나누어 주어서 팰린드롬 함수를 호출하는 횟수를 줄인 것도 뿌듯하다!!

 

하지만, 작은 곳에서 치명적인 실수를 많이 해 시간이 오래 걸린 게 아쉽다... 다음에는 이런 실수를 줄이기 위해 코드를 쓸 때도, 테스트를 할 때도 정신 똑바로 차리면서 문제를 풀어야겠다.