https://www.acmicpc.net/problem/1509
1509번: 팰린드롬 분할
세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하
www.acmicpc.net
[ 문제풀이 ]
먼저 dp라는 이차원 배열을 만들어서 팰린드롬인지 체크를 해야 합니다. dp [1][3]이 1이라면 문자열의 1번부터 3번까지는 팰린드롬이라는 뜻입니다.
그리고 어디부터 어디까지 팰린드롬인지 체크하기 위해서는 문자열의 끝에서부터 시작해야합니다.
먼저 글자가 하나일 때는 모든 글자가 팰린드롬이므로 dp [i][i]는 1로 채워줍니다.
그러고 나서 4번째 행부터 체크를 시작합니다. 나의 바로 앞까지 만약 팰린드롬인 문자열이 있다면 나와 팰린드롬인 문자열의 바로 앞 문자와 비교해서 같으면 나도 팰린드롬이라는 결과를 얻을 수 있습니다.
즉, dp [i+1][j-1]이 1이라면 i번째 문자열과 j번째 문자열이 같다면 dp [i][j]는 1이 됩니다.
이렇게 모든 dp배열을 채우면 몇 번 문자부터 몇번 문자까지 팰린드롬인지 모두 체크할 수 있고, 이것을 이용해서 팰린드롬을 최소 몇 개로 나타낼 수 있는지 구할 수 있습니다.
이번엔 반대로 앞에서부터 시작합니다.
ans배열을 만들고, 기록을 시작합니다. ans배열은 i번째 문자열까지 팰린드롬을 최소로 나눌 수 있는 수를 기록할 배열입니다.
만약 ans [i]의 값을 구하고 싶다면 j번부터 i번까지 팰린드롬인 문자열을 찾고, 만약 팰린드롬이라면 ans [i] 값과 ans [j-1]+1의 값을 비교해 더 작은 숫자를 대입해 줍니다. 왜냐하면 ans [j-1]은 j-1번째 문자열까지의 최솟값을 저장했기 때문입니다.
[ 소스 코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | #include <iostream> #include <string> using namespace std; string str; int dp[2501][2501]; //팰린드롬인지 판별할 배열 int ans[2501]; //최솟값을 저장할 배열 int main() { cin >> str; str = ' ' + str; for (int i = str.size(); i >= 1; i--) { //dp[start][end] start부터 end까지 팰린드롬이라면 1 아니라면 0 for (int j = str.size(); j >= i; j--) { if (i == j) dp[i][j] = 1; else if (j - i == 1) { if (str[i] == str[j]) { dp[i][j] = 1; } } else { if (dp[i + 1][j - 1] == 1) { if (str[i] == str[j]) { dp[i][j] = 1; } } } } } for (int i = 1; i <= str.size()-1; i++) { ans[i] = 3000; for (int j = 1; j <= i; j++) { if (dp[j][i] == 1) { //j부터 i까지 팰린드롬이라면 j-1의 값보다 1 더 크므로 ans[i] = min(ans[i], ans[j - 1] + 1); } //하지만 갱신이 되어있는 값이 더 작을 수도 있으므로 } //둘을 비교해서 더 작은 값을 대입 } cout << ans[str.size()-1]; } | cs |
'백준' 카테고리의 다른 글
| [ 백준 ] 10844번 - 쉬운 계단 수 (C++) (0) | 2022.05.28 |
|---|---|
| [ 백준 ] 2407번 - 조합 (C++) (0) | 2022.05.27 |
| [ 백준 ] 1208번 - 부분수열의 합 2 (C++) (0) | 2022.05.25 |
| [ 백준 ] 17387번 - 선분 교차 2 (C++) (0) | 2022.05.24 |
| [ 백준 ] 17143번 - 낚시왕 (C++) (0) | 2022.05.23 |