백준 1509 팰린드롬 분할 (c++) : 피너클

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

1509번: 팰린드롬 분할

다이나믹 문제다.

int n;
string str;
bool palindrome[2501][2501];
int cache[2501];

사용할 변수다.

palindrome[a][b]는 a부터 b까지의 string이 팰린드롬인지 아닌지를 알려준다.

true면 팰린드롬이고 false면 팰린드롬이 아니다.

cache는 dp에서 사용할것이다.

cin >> str;
n = str.length();
memset(cache, -1, sizeof(cache));
memset(palindrome, false, sizeof(palindrome));

값을 입력받은뒤 cache와 palindrome을 초기화한다.

for (int i = 0; i < n; i++) palindrome[i][i] = true;

모든 palindrome[i][i]을 true로한다.

'A', 'B', 'C'같이 하나만 있는 문자는 무조건 팰린드롬이다.

for (int i = 0; i < n - 1; i++)
	if (str[i] == str[i + 1]) palindrome[i][i + 1] = true;

그후 str[i] == str[i+1]이면 palindrome[i][i+1]을 true로한다.

'AA', 'BB'와 같은건 true로하고 'BC', 'BE'같은건 false로한다.

for (int i = 3; i <= n; i++) {
    for (int s = 0; s < n; s++) {
        if (s + i > n) break;
        int e = s + i - 1;
        if (str[s] == str[e] && palindrome[s + 1][e - 1]) palindrome[s][e] = true;
    }
}

이제 길이가 3이상인 것들을 파악할것이다. int i는 팰린드롬의 길이를 의미하고 s는 팰린드롬의 시작점을 의미한다.

만약 s + i가 n보다 크다면 범위를 벗어난것이니 반복문에서 빠져나온다.

int e는 팰린드롬의 끝점을 의미한다. 시작점이 0이고 길이가 3이면 끝점은 0 + 3 - 1인 2다.

이제 시작점과 끝점의 문자가 같고 그 사이가 팰린드롬이면 palindrome[s][e]는 true가된다.

A

A

위와 같이 시작점과 끝점이 같고

A

C

B

C

A

그 사이가 팰린드롬이면 이 문자열도 팰린드롬이 되는것이다. 이것을 끝까지 반복한다.

cout << solve(str.length() - 1) << '\n';

그후 solve함수를 돌려주면 된다.

int solve(int end) {
	if (end == -1) return 0;
	if (end == 0) return 1;

solve함수다. int end는 검사할 문자열의 끝점이다.

만약 end가 5라면 0부터 5까지를 검사할것이란 뜻이다.

만약 end가 -1이면 0을 반환하고 0이면 1을 반환한다.

	int &ret = cache[end];
	if (ret != -1) return ret;

만약 이전에 방문한 적이 있다면 그 값을 반환한다.

	int ans = 987654321;
	for (int i = 0; i <= end; i++) {
		if (palindrome[i][end]) ans = min(ans, solve(i - 1) + 1);
	}

그후 0부터 하나씩 돌며 만약 palindrome[i][end]가 팰린드롬이라면

ans와 solve(i-1) + 1을 비교해 더 작은걸 ans에 넣는다.

sole(i)가 아니고 solve(i-1)을 넣는 이유는 

A

B

C

A

A

위의 상황에서 end가 4고 int i가 3인 상황이라면 palindrome[3][4]는 true니 ans와 비교가 시작될것이다.

solve(3)을 하면

A

B

C

A

위를 검사하게 되는것이다. A를 한번더 검사하게 되는 것이다. 이런 중복을 막기위해 solve(i-1)을 하는것이다.

맨 위에서 if(end == -1) return 0이 있던 이유도 이와 연결된다.

end가 0인 상태에서 반복문이 돌아가면 ans = min(ans, solve(0 - 1) + 1)이 실행된다. solve(-1)이 실행되는것이다.

이런 예외를 처리하기 위해 end == -1을 추가한것이다.

	return ret = ans;
}

마지막으로 ret에 ans를 넣으며 반환한다.

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;

int n;
string str;
bool palindrome[2501][2501];
int cache[2501];

int solve(int end) {
	if (end == -1) return 0;
	if (end == 0) return 1;
	int &ret = cache[end];
	if (ret != -1) return ret;
	int ans = 987654321;
	for (int i = 0; i <= end; i++) {
		if (palindrome[i][end]) ans = min(ans, solve(i - 1) + 1);
	}
	return ret = ans;
}

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

	cin >> str;
	n = str.length();
	memset(cache, -1, sizeof(cache));
	memset(palindrome, false, sizeof(palindrome));

	for (int i = 0; i < n; i++) palindrome[i][i] = true;
	for (int i = 0; i < n - 1; i++)
		if (str[i] == str[i + 1]) palindrome[i][i + 1] = true;
	for (int i = 3; i <= n; i++) {
		for (int s = 0; s < n; s++) {
			if (s + i > n) break;
			int e = s + i - 1;
			if (str[s] == str[e] && palindrome[s + 1][e - 1]) palindrome[s][e] = true;
		}
	}

	cout << solve(str.length() - 1) << '\n';
}

전체코드다.