[백준] | C++ | 10942. 펠린드롬? (Top-down DP)

개요

골드 1을 달성했습니다.

 

그런 의미에서 이번에 푼 문제는 클래스 5의 문제인 10942. 펠린드롬? 입니다.

무슨 상관이냐구요? 클래스 5를 달면 플레를 더 빨리 갈 수 있거든요.

 

 

---

 

 

문제

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.

각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.

예를 들어, 홍준이가 칠판에 적은 수가 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개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

 

출력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

 

입력

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

 

테스트 케이스

입력	출력
7 1 2 1 3 1 2 1 4 1 3 2 5 3 3 5 7	1 0 1 1

 

 

---

 

 

풀이

아이디어 정리

일단 알고리즘 분류는 깡 DP입니다.

이러면 점화식만 떠올릴 수 있다면 쉽습니다.

 

일단 펠린드롬이 무엇인지부터 생각해봅시다.

앞으로 읽을때와 뒤로 읽을 때가 동일한 수를 의미하는게 펠린드롬이죠.

 

 

이때 펠린드롬의 특성을 하나 알 수 있습니다.

앞 뒤로 수를 하나씩 잘라내더라도 그 수는 여전히 펠린드롬입니다. 이걸 이용해서 DP를 짜볼 수 있어요.

 

 

일단 입력은 S와 E가 들어오죠. S번째 수 부터 E번째 수가 펠린드롬인지의 여부를 0과 1로 출력 하면 돼요.

그러면 1차원 배열의 DP로는 택도 없습니다. 2차원 배열을 사용해보죠.

 

dp[i][j]에 수열의 i번째 수 부터 j번째 수 펠린드롬을 이루는지에 대한 여부를 담을겁니다.

그리고 위의 특성을 이용하면 dp[i][j]가 성립하기 위해서는 dp[i+1][j-1]이 성립함과 동시에 수열의 i번째 수와 j번째 수가 동일해야 한다는걸 알 수 있습니다.

 

그러니 수열을 seq라고 선언했을때 점화식은 다음과 같이 나옵니다.

dp[i][j] = dp[i+1][j-1] && seq[i] == seq[j]

 

 

코드로 풀기

아이디어는 전부 나왔죠? 그러면 코드는 쉽습니다.

일단 입력을 전부 받아줍시다.

 

dp는 모두 -1로 초기화 해둡니다

int n;
cin >> n;

vector<int> seqVec(n + 1);
vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));
for (int i = 1; i <= n; i++)
{
	cin >> seqVec[i];
}

int m;
cin >> m;
for (int i = 0, s, e; i < m; i++)
{
	cin >> s >> e;
}

 

 

저는 이번 문제 풀이에서 Bottom-up 대신 Top-down 이라는 기법을 사용해볼겁니다.

둘의 차이점은 속도인데 솔직히 거기서 거기에요. 시간 복잡도는 Bottom-up이 \(O(n^2)\)이고 Top-down이 \(O(n^2+m)\)으로 Top-down이 더 느려요. 근데 테스트케이스에 따라 Top-down이 더 빠르기도 합니다.

왜 이렇게 차이가 나냐면 Bottom-up은 dp배열을 미리 꽉꽉 채워넣는데 Top-down은 들어온 입력에 따라 실시간으로 dp배열을 채우기 때문이에요. Top-down은 함수 호출 등의 오버헤드 때문에 상수 시간 \(O(1)\)을 테스트 케이스의 개수인 M개만큼 더해서 더 느립니다.
구현도 Top-down이 조금 더 길어요.

아무튼 제가 Top-down을 이번에 시도해본 이유는 그냥 적다보니까 Top-down이 돼있었어요.

 

 

아무튼 이제 핵심 함수인 checkPelindrome 함수를 적어줍시다.

bool checkPelindrome(vector<int>& seq, vector<vector<int>>& dp, int s, int e)

 

이렇게 함수 적을때마다 드는 생각인데 그냥 전역 배열을 두는게 더 괜찮아보이는 것 같습니다.

 

아무튼 이 함수는 s와 e를 받아서 수열의 s번째 수 부터 e번째 수 까지가 펠린드롬인지의 여부를 반환합니다.

 

 

일단 dp[s][e]가 이미 계산 되어있다면 그걸 반환합니다. 이거 없으면 메모이제이션이 아니에요.

if (dp[s][e] != -1)
	return dp[s][e];

 

그리고 몇가지 분기를 체킹해야 합니다.

s와 e가 같은 경우 그 수는 무조건 펠린드롬입니다. 왜냐하면 그냥 수열에 수가 하나밖에 없어서 어디로 읽던간에 무조건 똑같거든요.

 

그리고 만약 s와 e의 차가 1, 그러니까 [1 2] 라던가 [2 3] 같이 수열의 길이가 2가 된다면 seq[s]와 seq[e]가 같은지만 체킹해주면 돼요.

이런식으로 대입과 동시에 반환해주면 됩니다.

if (s == e)
	return dp[s][e] = 1;
if (s == e - 1)
	return dp[s][e] = seq[s] == seq[e];

 

 

그리고 그 무엇도 아니라면 재귀를 돌리면 됩니다. s는 한칸 전진하고 e는 한칸 후진해서 말이죠. 그리고 s+1과 e-1이 펠린드롬이라고 해도 seq[s]와 seq[e]가 같지 않다면 펠린드롬이 아니기 때문에 and 연산을 해줍시다.

return dp[s][e] = checkPelindrome(seq, dp, s + 1, e - 1) && (seq[s] == seq[e]);

 

그러면 checkPelindrome 함수가 완성됩니다.

 

그러면 이제 출력만 해주면 돼요.

for (int i = 0, s, e; i < m; i++)
{
	cin >> s >> e;

	cout << checkPelindrome(seqVec, dp, s, e) << '\n';
}

 

 

 

---

 

 

마치는 말

Top-down DP를 외판원 순회에서 사용해보면서 이번에 그 반동으로 복습이 되었는데 생각보다 이것도 괜찮네요.

재귀라는게 처음 접할땐 그냥 공포의 대상인데 은근히 재밌습니다.

 

 

---

 

 

코드 전문

bool checkPelindrome(vector<int>& seq, vector<vector<int>>& dp, int s, int e)
{
	if (dp[s][e] != -1)
		return dp[s][e];
	if (s == e)
		return dp[s][e] = 1;
	if (s == e - 1)
		return dp[s][e] = seq[s] == seq[e];

	return dp[s][e] = checkPelindrome(seq, dp, s + 1, e - 1) && (seq[s] == seq[e]);
}

int main()
{
	FAST_PRINT;

	//dp[i][j] = 수열의 i번째 수 부터 j번째 수가 펠린드롬 수면 1 아니면 0
	//dp[i][j] = dp[i+1][j-1] && seq[i] == seq[j];

	int n;
	cin >> n;

	vector<int> seqVec(n + 1);
	vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));
	for (int i = 1; i <= n; i++)
	{
		cin >> seqVec[i];
	}

	int m;
	cin >> m;
	for (int i = 0, s, e; i < m; i++)
	{
		cin >> s >> e;

		cout << checkPelindrome(seqVec, dp, s, e) << '\n';
	}
}