2 초 | 512 MB | 2037 | 666 | 554 | 34.389% |
팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다.
승수는 주어진 문자열의 부분수열 중 팰린드롬이 되는 부분수열의 개수를 알고싶어한다. (공집합은 포함하지 않는다)
예를들어 'abb' 의 부분수열은 {'a'}, {'b'}, {'b'}, {'ab'}, {'ab'}, {'bb'}, {'abb'} 이고 이 가운데 팰린드롬은 {'a'}, {'b'}, {'b'}, {'bb'} 으로 4개 이다.
문자열이 주어졌을 때, 팰린드롬이 되는 부분수열의 개수를 출력하는 프로그램을 작성하시오.
첫째 줄에 길이가 1000을 넘지 않는 문자열 S 가 주어진다. 문자열 S는 알파벳 소문자로만 이루어져 있다.
주어진 문자열 S 의 부분수열 중 팰린드롬이 되는 부분수열의 개수를 10,007 로 나눈 나머지를 출력한다.
abb
4
https://www.acmicpc.net/problem/14517
주어진 문자열 S에서 나올 수 있는 부분수열 중 팰린드롬이 되는 것의 개수를 구하는 문제이다.
부분 수열이라는 것을 깊게 생각하지 않으면 나처럼 처음에 틀린 답을 내놓을 수 있다.
예를 들면 S = "aba"가 주어졌을 때 나는 {a}, {b}, {a}, {aba} 4개가 정답이라 생각했는데 부분 수열이란 꼭 서로 붙어있는 요소끼리 묶으란 법이 없으므로 {aa}와 같이 중간을 건너뛴 팰린드롬도 다 세줘야한다.
따라서 S = "aba"인 경우에는 {a}, {b}, {a}, {aa}, {aba} 이렇게 5개의 팰린드롬 부분 수열을 만들 수 있다.
그래서 어떻게 팰린드롬의 개수를 구할 수 있을까? 이는 이전 팰린드롬 문제에서 풀었던 것처럼 DP를 이용하면 쉽다.
문자열 S의 길이가 N일때 길이가 1일때부터 N일때까지 순서대로 구하면 된다.
이떄 우리는 int 2차원 배열 dp를 만들어 사용할 것이다. 배열 dp의 정의는 다음과 같다.
dp[i][j] = index가 i ~ j 일때 그 안에 존재하는 팰린드롬 부분 수열의 개수
길이 L = 1일 때부터 L = N이 될 때까지 다음과 같은 방법으로 dp를 진행한다.
L = 1일때는 모든 글자가 팰린드롬이므로 dp[i][i] = 1로 만들어준다.
L = 2일때는 두 글자가 같으면 dp[i][i + 1] = 3, 다르면 dp[i][i + 1] = 2로 만들어준다.
L = 3이상인 경우는 다음 규칙에 따른다.
1. 우선 index i와 j를 정의한다. i = 0, j = i + (L - 1)이고 이는 i ~ j의 부분 문자열 s를 의미한다.
2. i와 j를 1씩 증가시켜 길이 = L일때 만들 수 있는 모든 s에서 팰린드롬의 부분 수열의 개수를 구한다.
3. 만약 S의 i번째 글자와 j번쨰 글자가 다르면
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
같으면
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + (dp[i + 1][j - 1] + 1);
이렇게 dp[i][j]를 구해준다.
이때 사용되는 것이 포함 배제의 원리로 i ~ j - 1의 팰린드롬 개수와 i + 1 ~ j의 팰린드롬 개수를 더하면 i + 1 ~ j - 1의 팰린드롬 개수가 2번 더해졌으므로 1번 빼줘야한다. 만약 i번째와 j번째 글자가 같으면 양쪽 글자 2개를 두고 가운데 올 수 있는 팰린드롬 개수 + 1만큼 더해줘야한다.
이렇게 부분 수열에 대한 이해도와 포함 배제의 원리, 그리고 팰린드롬 개수를 DP를 통해 세는 법만 알면 문제를 어렵지 않게 풀 수 있다.
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
int n = s.length();
int[][] dp = new int[n][n];
int mod = 10007;
for (int i = 0; i < n; i++)
dp[i][i] = 1;
for (int i = 1; i < n; i++){
dp[i - 1][i] = 2;
if (s.charAt(i) == s.charAt(i - 1))
dp[i - 1][i]++;
}
for (int i = 2; i < n; i++){
for (int j = i; j < n; j++){
if (s.charAt(j) == s.charAt(j - i)){
dp[j - i][j] = (dp[j - i][j - 1] + dp[j - i + 1][j] + 1) % mod;
} else{
dp[j - i][j] = (mod + dp[j - i][j - 1] + dp[j - i + 1][j] - dp[j - i + 1][j - 1]) % mod;
}
}
}
System.out.println(dp[0][n - 1]);
}
}
백준 1655 [가운데를 말해요] (4) | 2023.10.15 |
---|---|
백준 14939 [불 끄기] (0) | 2023.07.05 |
백준 12850 [본대 산책2] (0) | 2023.07.03 |
백준 16566 [카드 게임] (0) | 2023.07.01 |
백준 2887 [행성터널] (1) | 2023.06.27 |