[BOJ/백준 10942/C++] 펠린드롬?

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

10942번: 팰린드롬?

 

[문제 요약]

N개의 자연수가 주어지고 이후로 M개의 질문이 들어온다.

질문의 형태는 두 자연수 S와 E가 주어진다. ( 1 ≤ S ≤ E ≤ N )

주어진 N개의 자연수에 대하여 S번째 수부터 E번째 수까지 수가 팰린드롬이면 1, 아닌 경우 0을 출력한다.

 

예를 들어, 주어진 자연수들이 1, 2, 1, 3, 1, 2, 1라고 하자.

• S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
• S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
• S = 3, E = 3인 경우 1은 팰린드롬이다.
• S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.

[문제 조건]

N ( 1 ≤ N ≤ 2000) , 주어지는 자연수들은 100,000 보다 작거나 같은 자연수.

M ( 1 ≤ M ≤ 1,000,000)

시간제한 : 0.5초

메모리제한 : 258MB

 

[문제 풀이]

(dp는 dp테이블, dt는 주어진 자연수들을 담은 배열)

제한시간 0.5초인걸 보고 DP(Dynamic Programming)을 이용해야겠다는 걸 바로 알아차렸다.

그 다음 1차원dp로 풀릴 수 있나 잠깐 고민해봤지만 뭔 짓을해도 답을 구할 수가 없을 거 같아서 바로 2차원 dp의 형태로 생각을 해나갔다.

 

먼저 가장 중요한 dp 테이블의 값을 어떻게 정의를 내릴것인가?

본인은 dp 테이블의 값을 dp[i][j] = i번째 수부터 j번째 수까지의 수가 팰린드롬인지 아닌지 여부로 설정했다.

 

값을 정의 하고 난 뒤 한참동안 어떻게 풀어야 될지 고민을 하다가 그냥 예제를 그려보기로 결정했다.

		1	2	1	3	1	2	1
		[1]	[2]	[3]	[4]	[5]	[6]	[7]
1	[1]	o	x	o	x	x	x	o
2	[2]		o	x	x	x	o	x
1	[3]			o	x	o	x	x
3	[4]				o	x	x	x
1	[5]					o	x	o
2	[6]						o	x
1	[7]							o

위 표와 같이 나타낼 수 있다.

 

그래서 일단 처음에 생각했던 방법은

[1][1] , [2][2] ....... [n][n] -> [1][2] , [2][3] , [3][4] .... [n-1][n] 과 같이 좌상단에서 우하단 방향 대각선 순서로 확인하면서

시작과 끝의 수가 같고 내부의 수가 모두 팰린드롬이면 현재 값도 팰린드롬이다. 라는 방식을 썻었다.

ex) dp[i][j]를 구한다고 가정하면 dt[i] 와 dt[j]의 값이 같아야되고 , i+k<=j-k의 조건을 만족하면서 dp[i+k][j-k] ( k는 0보다 큰 자연수) 의 값이 모두 true일때 dp[i][j]의 값도 true로 설정했다.

 

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

using namespace std;

int N, q_cnt;
vector<int> dt;
vector<vector<bool>> dp;

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

	cin >> N;
	dt.resize(N + 1);
	dp.resize(N + 1);
	for (int i = 0; i <= N; i++) dp[i].resize(N + 1);

	for (int i = 1; i <= N; i++) cin >> dt[i];

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

			if (dt[j] != dt[j + i]) dp[j][j + i] = false;
			else
			{
				bool flag = true;
				for (int k = 1; j + k < j + i - k; k++)
				{
					if (dp[j + k][j + i - k] == false) { flag = false; break; }
				}
				if (flag) dp[j][j + i] = true;
				else dp[j][j + i] = false;
			}
		}
	}

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

하지만 확인하는 값들이 너무 많아서 그런지 시간초과가 떳다........

 

문제를 풀때마다 시간초과, 틀렸습니다를 볼때마다 화가 난다. 하지만 풀었을때 그 쾌감은 매우 짜릿하기 때문에  계속 풀어보도록 하자

 

시간초과가 났다는건 확인하는 테이블을 줄이면 해결되지 않을까...? 라는 생각을 먼저했다.

아까 만든 표를 다시 보면

이 처럼 뭔가 쭉 뻗어 가는 규칙이 보인다

[4][4] 를 기준으로 보면 [4][4] -> [3][5] -> [2][6] -> [1][7]이 된다

한 자리 수를 기준으로 양 옆으로 퍼져나갈때 양 끝이 같은 수면 팰린드롬이라는 소리다!

 

그렇게 작성한 코드가 

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

using namespace std;

int N, q_cnt;
vector<int> dt;
vector<vector<bool>> dp;

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

	cin >> N;
	dt.resize(N + 1);
	dp.resize(N + 1);
	for (int i = 0; i <= N; i++) dp[i].resize(N + 1);

	for (int i = 1; i <= N; i++) cin >> dt[i];

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

		for (int k = 1; i - k >= 1 && i + k <= N; k++)
		{
			if (dt[i - k] != dt[i + k]) break;
			else dp[i - k][i + k] = true;
		}
	}

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

근데 얘는 아예 틀렸단다. 왜? 도대체? 뭐가 빠진거지?

 

그래서 다시 표를 보고 생각하던 와중

1, 2, 2, 1 이런 배열이 있으면 저 코드는 과연 팰린드롬이라고 생각하는가?

당연히 아니라고 했을거다. 왜냐면 어떤 한 수를 잡고 양옆으로 한칸씩 이동하면서 같은 수 인지 확인하면 같은 경우가 없기 때문에 false를 띄웠을 것이다.

 

당연히 위 코드도 틀렸다는 것이다. 

 

다시 생각해보니 위의 방식은 홀수 길이의 수만 확인이 가능하지 짝수 길이의 수는 확인이 불가능하다는 것을 깨닫게 되었다.

그러면 짝수 길이는 어떻게 해결하냐

위에 파란색선과 같은 원리로 똑같이 진행해주면 된다.

 

[소스코드]

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

using namespace std;

int N, q_cnt;
vector<int> dt;
vector<vector<bool>> dp;

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

	cin >> N;
	dt.resize(N + 1);
	dp.resize(N + 1);
	for (int i = 0; i <= N; i++) dp[i].resize(N + 1);

	for (int i = 1; i <= N; i++) cin >> dt[i];

	for (int i = 1; i <= N; i++)
	{
		dp[i][i] = true;
		for (int k = 1; i - k >= 1 && i + k <= N; k++)
		{
			if (dt[i - k] != dt[i + k]) break;
			else dp[i - k][i + k] = true;
		}
	}

	for (int i = 1; i < N; i++)
	{
		if (dt[i] != dt[i + 1]) { dp[i][i + 1] = false;  continue; }
		else
		{
			dp[i][i + 1] = true;
			for (int k = 1; i - k >= 1 && i + 1 + k <= N; k++)
			{
				if (dt[i - k] != dt[i + 1 + k]) { break; }
				else dp[i - k][i + 1 + k] = true;
			}
		}
	}
	cin >> q_cnt;
	for (int i = 0; i < q_cnt; i++)
	{
		int s, e;
		cin >> s >> e;
		cout << dp[s][e] << "\n";
	}
}

 

 

굳