풀이
문자열의 끝 문자가 추가 되거나 삭제 될 때, 매번의 추가/삭제 이후에 모든 부분 팰린드롬의 개수를 빠르게 구해야 한다.
문자가 추가/삭제 된다는 조건과 쿼리 문제라는 생각에 뭔가 어려워 보인다.
문자가 끝에서만 추가되고 삭제되기 때문에, 그냥 fix된 문자열에서 다이나믹으로 팰린드롬 구하는 O(n^2) 알고리즘을 그대로 가져오면 된다.
시간 제한이 1초여서 조금 빡빡한 듯 하지만, 엄밀히 따져보면 10000^2에 나누기 상수가 붙어서 1초 보다 좀 덜 돈다. (그리고 컴파일러 -o2 최적화가 붙으면 간단한 10000^2정도는 1초에 충분히 돌아가기도 한다)
O(4 * n^2)으로 짜면 시간 초과가 (아마?) 날 거고, 나는 다음과 같이 풀었다:
chk[i][j] = i번째 문자부터 j번째 문자까지가 팰린드롬인지 여부
chk[i][j] = 1 && str[i-1] = str[j+1] => chk[i-1][j+1] = 1
이런 느낌으로, 정확히는 코드를 보는 게 이해하기 더 좋을 것 같다.
사실 내 코드는 chk[i][j] = i번째 문자부터 i+j번째 문자까지가 팰린드롬인지 여부로 되어있는데, 어쩌다가 풀다 보니 그렇게 됐는데 고치기 귀찮아서 그냥…
나와 같은 방법으로 풀 것이라면, '-'가 들어왔을 때 chk 배열 초기화에 유의하자.
코드
#include <cstdio>
int q, len, dp[10003];
char c, str[10003];
bool chk[10003][10003];
int main() {
scanf("%d ", &q);
while (q--) {
scanf("%c", &c);
if (c == '-') {
dp[len] = 0;
for (int i = 1; i < len; i++) {
chk[i][len-i] = chk[len][i] = 0;
}
printf("%d ", dp[--len]);
continue;
}
str[++len] = c;
dp[len] = dp[len-1] + 1;
chk[len][0] = 1;
if (str[len-1] == c) {
dp[len]++;
chk[len-1][1] = 1;
}
for (int i = 2; i < len; i++) {
if (!chk[i][len-i-1] || str[i-1] != c) {
continue;
}
dp[len]++;
chk[i-1][len-i+1] = 1;
}
printf("%d ", dp[len]);
}
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이