[백준 14517번 C/C++] 팬린드롬 개수

 

[백준 14517번 C/C++] 팬린드롬 개수 

 

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

14517번: 팰린드롬 개수 구하기 (Large)

---

 

해결전략

 

팰린드롬 Palindrome

포함 배제의 원리

동적계획법 Dynamic Programming

---

 

처음 시도한 코드 - 시간초과

 

 

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <unordered_set>
using namespace std;

string s;
unordered_multiset<string> mySet;
vector<int> ch;
vector<vector<int>> dp;

int countPalindrome(const string& str, int start, int end)
{
    if (start >= end) return 1;
    if (dp[start][end] != -1) return dp[start][end];

    if (str[start] == str[end])
    {
        dp[start][end] = countPalindrome(str, start + 1, end - 1);
        return dp[start][end];
    }
    else
    {
        dp[start][end] = 0;
        return 0;
    }
}

void DFS(const string& str, int idx)
{
    //cout << "str = " << str << "\n";

    if (countPalindrome(str, 0, str.size() - 1))
    {
        mySet.insert(str);
    }

    if (str.size() == s.size())
    {
        return;
    }

    for (int i = idx; i < s.size(); i++)
    {
        if (ch[i] == 0)
        {
            ch[i] = 1;
            DFS(str + s[i], i+1);
            ch[i] = 0;
        }
    }
}

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

    ch.resize(s.size());
    dp.resize(s.size(), vector<int>(s.size(), -1));

    DFS("", 0);

    cout << mySet.size() % 10007;

    return 0;
}

 

---

 

정답 코드

 

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

const int MOD = 10007;  // 모듈로 연산을 위한 상수 정의
string s;               // 입력받을 문자열
vector<vector<int>> dp; // dp[a][b]는 [a, b] 구간에서의 팬린드롬의 개수를 저장

int DFS(int a, int b)
{
    if (a > b) return 0;   // 시작 인덱스가 인덱스보다 크면 0 반환
    if (a == b) return 1;  // 시작 인덱스와 끝 인덱스가 같으면 1 반환 (자기 자신은 팬린드롬)
    if (dp[a][b] != -1) return dp[a][b];  // 이미 계산된 값이면 그 값을 반환

    // 팬린드롬의 개수 계산
    dp[a][b] = (DFS(a, b - 1) + DFS(a + 1, b) - DFS(a + 1, b - 1)) % MOD;

    if (dp[a][b] < 0) // 모듈로 연산 결과가 음수이면 MOD를 더해줌
        dp[a][b] += MOD;

    ifs[a] == s[b]) // 시작 문자와 끝 문자가 같으면 추가로 팬린드롬의 개수를 더해줌
        dp[a][b] = (dp[a][b + DFS(a + 1, b - 1) + 1) % MOD;

    return dp[a][b] % MOD;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> s;
    
    dp.resize(s.size(), vector<int>(s.size(), -1)); // dp 배열 크기를 문자열의 길이만큼 설정하고, 초기값을 -1로 설정

    cout << DFS(0, s.size()-1) % MOD;

    return 0;
}

 

 

 

 

---