이번 문제는 백준의 골드 4 문제 팰린드롬? 이다.
문제를 한번 차근차근 읽어보자!
최대 100,000까지의 수가 2000개까지 칠판에 주어진다.
이 때, 두 정수 S, E로 질문을 던지게 된다.
S부터 E까지의 구간을 자르면, 팰린드롬인가?
질문의 수는 최대 1,000,000개가 주어질 수 있다.
질문에 올바르게 답해보세요!
문제 분석
우선 질문의 수가 1,000,000개 까지로 굉장히 많다.
무턱대고 완전탐색으로 팰린드롬을 검사하면 시간초과가 날 것이 분명하다.
그럼 이 문제의 핵심은 팰린드롬을 빠르게 판단하는 것!
매번 팰린드롬인지 검사를 할 수 없으니, 저장을 해야할 것 같다.
그럼 DP의 누적합과 유사하게 배열에 저장을 해나가는 것이 맞을 것 같다.
이제 관건은 어떤 방식으로 모든 구간이 팰린드롬인지 저장할 것인가?!
DP
나는 2차원 DP 배열을 선언해서 문제를 풀어볼까 한다.
각 칸, 즉 DP[i][j]가 의미하는 바는 i ~ j 구간이 팰린드롬인지를 의미하도록 한다.
가장 먼저 길이가 1인 경우는, 반드시 팰린드롬이다.
아래와 같이 로직을 구현할 수 있을 것이다.
for (int i = 1; i <= num; i++) {
dp[i][i] = 1; // 1자리 수는 반드시 팰린드롬
}또한, 길이가 2인 경우도 해당 과정에서 추려낼 수 있다.
길이가 2가 되려면 i - 1번째 수와 i번째 수가 동일해야 한다.
즉, 아래와 같이 함수를 만들 수 있을 것이다.
for (int i = 1; i <= num; i++) {
dp[i][i] = 1; // 1자리 수는 반드시 팰린드롬
if (i == 1)
continue;
if (num_arr[i - 1] == num_arr[i])
dp[i - 1][i] = 1; // 2자리 수는 앞뒤로 같아야 함
}이제 나머지 칸은 어떤 방식으로 채울 수 있을까?
길이가 3 이상인 수열에 대해서는 어떻게 팰린드롬을 검사할까?
잠깐 생각해보면 우선 질의에 들어온 두 구간에 대해서는 값이 같아야 할 것이다.
다시 말해, arr[i] == arr[j] 여야 한다는 말이다.
그리고 하나 더, 확실하게 팰린드롬이 되려면 그 내부도 팰린드롬이어야 한다.
다시 말해, dp[i+1] == dp[j-1]이 성립한다면, 팰린드롬이 된다는 말이다.
이제 조건은 생각했으니, 배열을 어떤 순서로 채워 나갈지를 생각해야 한다.
이 부분이 굉장히 고민이었다.
처음엔 이중 for문을 통해 순회하려고 했다.
for (int i = 1; i <= num - 2; i++) {
for (int j = i + 2; j <= num; j++) {
if (num_arr[i] == num_arr[j] && dp[i + 1][j - 1] == 1)
dp[i][j] = 1;
}
}위와 같이 i를 1부터 num - 2까지 순회한다.
안쪽은 j을 i + 2부터 num까지 순회하도록 한다.
그 이유는, 이 탐색은 길이가 3이상인 팰린드롬을 탐색하는 것이기 때문이다.
i ~ i + 2부터 i ~ num까지 길이를 모두 검사하려고 했다.
하지만 안타깝게도 정답을 맞추지 못했다.
어떤게 문제인지 도저히 생각이 나지 않아, 다른 사람의 풀이를 참고했다.
채우는 순서
그림을 그려보니, 얼마나 바보인지 단번에 이해할 수 있었다.
기본적으로 1, 2 길이의 팰린드롬을 채우고 나면 아래와 같은 표가 된다.
만약 위에서부터 채운다고 생각하면 어떻게 될까?
dp[i + 1][j - 1]의 의미를 한번 잘 생각해보면, 이는 왼쪽 대각선 아래를 의미한다.
그럼 내가 채우는 순서대로 채우면, 표가 아래와 같이 되는 것이다.
5번 칸부터는 왼쪽 대각선 아래가 값이 없어 채울수가 없다.
따라서 우리는 i를 가장 아래쪽부터 채우기 시작해야 함을 알 수 있다.
바로 아래의 표와 같은 순서로 말이다.
최종적으로 코드는 아래와 같이 구현된다.
cin >> num;
for (int i = 1; i <= num; i++)
cin >> num_arr[i];
for (int i = 1; i <= num; i++) {
dp[i][i] = 1; // 1자리 수는 반드시 팰린드롬
}
for (int i = 1; i <= num - 1; i++) {
if (num_arr[i + 1] == num_arr[i])
dp[i][i+1] = 1; // 2자리 수는 앞뒤로 같아야 함
}
for (int i = num - 2; i >= 1; i--) {
for (int j = i + 2; j <= num; j++) {
if (num_arr[i] == num_arr[j] && dp[i + 1][j - 1] == 1)
dp[i][j] = 1;
}
}
cin >> query_num;
int from = 0, to = 0;
for (int i = 0; i < query_num; i++) {
cin >> from >> to;
cout << dp[from][to] << '\n';
}역시 DP는 아직도 어렵다.