[백준] 10942 - 팰린드롬?

10942. 팰린드롬？ 풀이

난이도: Gold IV
문제 주소: https://www.acmicpc.net/problem/10942

문제 풀이

이 문제는 칠판에 적힌 자연수 N개에 대해 S번째 수부터 E번째까지 수가 팰린드롬을 이루는지 묻는 질문을 총 M번 처리해야 하는 문제이다. 처음에는 재귀 함수와 메모이제이션을 활용한 Top-down DP 방식으로 코드를 작성했다.

 

int palindrom(int s, int e)
{
    if (s >= e) return 1;
    
    if (recall[s][e] != 0) return recall[s][e];
    if (num[s] == num[e]) return recall[s][e] = palindrom(s + 1, e - 1);
    else return recall[s][e] = -1;
}

이런 구조로 문제를 풀게 되면 주어진 구간의 양 끝 값이 같을 때 안쪽 구간을 재귀적으로 확인하며 팰린드롬이 아니면 -1을 반환하고 출력할 때 0으로 바꾸는 식이라 정답 처리는 무사히 되었다. 하지만 이렇게 풀게 되면 M개의 질문마다 매번 재귀 함수를 깊게 호출해야 할 수도 있어서 문제에서 의도한 최적의 풀이는 이게 아닐 것 같다는 생각이 들었다. 이 문제점을 보완하고자 바텀업 방식의 다음 풀이로 변경을 했다.

 

for (int i = 1 ; i <= n; i++) {
    for (int j = 1; j + i<= n; j++){
        if (num[j] == num[j + i]) {
            if (i == 1) dp[j][j + i] = 1;
            else if ( dp[j + 1][j + i -1] == 1)dp[j][j + i] = 1;
        }
    }
}

 

이번에는 질문을 받기 전에 미리 모든 구간에 대한 팰린드롬 여부를 dp 배열에 구해두는 방식을 사용했다. 구간의 길이를 의미하는 i를 1부터 늘려가면서 양 끝 값인 num[j]와 num[j + i]가 같고 그 내부 구간이 팰린드롬(dp[j + 1][j + i -1] == 1)이라면 현재 구간도 팰린드롬이 되도록 1로 업데이트한다.

그리고 양 끝 값이 같을 때 i == 1인 길이 2의 구간은 내부 구간이 없으므로 바로 1로 업데이트했다 그보다 긴 구간일 때는 이미 이전 루프에서 짧은 길이의 내부 구간 팰린드롬 여부가 계산되어 있으므로 그 값을 바로 참조하게 된다.

결과적으로 M번의 질문에 대해 dp[s][e]를 참조하여 팰린드롬이면 1, 아니면 0을 출력하며 시간 지연 없이 바로바로 답이 나온다.
처음 푼 재귀 풀이도 정답이긴 했지만 이렇게 바텀업으로 미리 다 구해두는 게 더 안정적이고 문제의 의도에 맞는 풀이 인거같다

최종 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <queue>
#include <stack>
#include <string>
#include <unordered_map>

using namespace std;
int num[2001];
int dp[2001][2001];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> num[i];
        dp[i][i] = 1;
    }

    for (int i = 1 ; i <= n; i++) {
        for (int j = 1; j + i<= n; j++){
            if (num[j] == num[j + i]) {
                if (i == 1) dp[j][j + i] = 1;
                else if ( dp[j + 1][j + i -1] == 1)dp[j][j + i] = 1;
            }
        }
    }
    int t;
    cin >> t;
    while (t--) {
        int s, e;
        cin >> s >> e;
        cout << dp[s][e] << "\n";
    }
}

---

'Algorithm > 백준' 카테고리의 다른 글

[백준] 9663 N－Queen  (0)	2026.04.01
[백준] 10814 - 나이순 정렬  (0)	2026.04.01
[백준] 2166 - 다각형의 면적 풀이  (0)	2026.03.22
[백준] 12851 - 숨바꼭질2  (0)	2026.03.19
[백준] 12865 - 평범한 배낭  (0)	2026.03.17