백준 1509 C++

• 팰린드롬이란,
  • 회문(回文) 또는 팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters)
• 팰린드롬 알고리즘
  • 첫 문자와 끝 문자부터 시작하여 차례차례 비교: O(N)의 시간복잡도
    1) Brute Force: 존재하는 모든 부분 문자열에 대해 회문 여부 검사
    2) Dynamic Programming: Memoization = 가장 작은 부분의 해답을 구한 뒤 이를 저장하고, 저장한 값을 이용하여 상위 문제를 해결 -> 시간복잡도가 더 낮으므로, 이 방법으로 코드 작성

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

using namespace std;

int n; // 입력된 문자열 길이
string str; // 입력된 문자열
bool dp[2501][2501]; // 팰린드롬 여부를 저장하는 2차원 배열
int cache[2501]; // 메모이제이션 배열

// 팰린드롬 최솟값 계산
int solve(int end) {
    if (end == 0) return 1;  // 한자리 수는 자기자신을 회문으로 가짐

    int &ret = cache[end];
    
    // ret가 -1이 아니면 ret를 리턴
    if (ret != -1) return ret;

    int ans = 987654321; // 계산 전 큰 숫자를 ans에 담아둠

    //  dp[i][end]가 true이면 ans를 solve 함수의 리턴값+1로 업데이트
    for (int i = 0; i <= end; i++) {
        if (dp[i][end])
        {
        	ans = min(ans, solve(i-1) + 1);
        }
    }

    // memoize 후 리턴
    return ret = ans;
}

int main()
{
	// 입출력 시간 단축
    ios::sync_with_stdio(0);  // stdio 버퍼와의 동기화를 비활성화
    cin.tie(0);  // cin과 cout의 묶음을 해제 (입력이 완료되지 않았어도 출력 가능, 알고리즘 계산 시에는 화면 출력이 중요하지 않으므로)
    cout.tie(0);

    // 입력
    cin >> str;
    n = str.length();

    // 배열 초기화
    memset(cache, -1, sizeof(cache));
    memset(dp, false, sizeof(dp));

    // 자기 자신은 모두 회문
    for (int i = 0; i < n; i++)
    {
    	dp[i][i] = true;
    }

    // str[i]와 str[i+1]이 같다면, dp[i][i+1]은 회문 (aa, cc)
    for (int i = 0; i < n - 1; i++)
        if (str[i] == str[i + 1])
        {
        	dp[i][i+1] = true;
        }

    // 글자수 3자리 이상일 때
    for (int i = 3; i <= n; i++) {
    	// 부분 문자열 확인하기
        for (int s = 0; s < n - i + 1; s++) 
        {
        	// 마지막 문자열 인덱스
            int e = s + i - 1;
			
            // 첫 문자열과 끝 문자열이 같고
            // 인접 dp가 true일 때
            if (str[s] == str[e] && dp[s + 1][e - 1]) 
            {
                dp[s][e] = true;
            }
        }
    }

    // 결과 출력
    cout << solve(str.length() - 1) << '\n';
}