[C++]10942: 팰린드롬?

요약

재귀 + dp

풀이과정

시간복잡도를 보기위해 최악의 경우를 본다면 숫자 2000, 질문 100만이며 0.5초를 요구한다.

숫자 2000 기준으로 본다면 O(n^2)는 가능한 범위에 들어온다.

즉 2중 반복문으로 모든 숫자에 대해 팰린드롬인지 아닌지를 확인하고 이를 저장한다면

이후 무슨 질문이 나오던지간에 O(1)으로 팰린드롬 여부를 확인할 수 있기 때문에 위배되지 않을 것이다.

 

모든 숫자의 조합에 접근하는 순간 O(n^2)를 충족하기 때문에

범위에 대한 펠린드롬 파악 방법은 무조건 O(1)이어야 함.

이는 팰린드롬의 특성을 고려하면 쉽게 해결가능하다.

 

일단 dp[n+1][n+1](1부터 시작하니까..)에 저장한다고 치고

 

질문에서 요구하는 답의 형식(1:팰린드롬임, 0:팰린드롬아님)으로 보면

숫자가 1개일때 -> 1 -> O(1)

숫자가 2개일때 -> 같으면 1, 다르면 0 -> O(1) 임은 쉽게 알 수 있다.

 

숫자가 3개이상일때부터는 같은 패턴을 보이는데,

1. 빨간색끼리 같으면 1, 다르면 0 -> O(1)

2. 보라색 범위가 팰린드롬인가?

의 AND 조건이라는 점이다.

2번의 경우, 범위 크기를 1부터 늘리는 방향으로 진행해왔기 때문에 보라색 범위는 이미 전 단계에서 구해서 저장했다. 그 값을 가져오면 되니 O(1)이다.

 

문제는 모든 조건을 구할 때 범위가 좀 드럽다는 점인데...

대각선 방향 진행으로 우상단 방향 반복문을 진행해야 함

이는 한 대각선의 row, col값의 합이 같다는 점을 이용해 row, col을 관리하면 되지만...

 

나는 그냥 위의 패턴을 이용해 재귀로 풀었다.

왜냐면 질문에서 다 요구할지 안할지도 모름

표 다 채우려면 범위가 귀찮음

 

map[n+1][n+1]은 -1로 모두 초기화하였다. -1은 아직 기록되지 않았다는 뜻이다.

bool isF2(int a, int b)
{
    if(map[a][b] != -1)	//이미 저장된 여부가 있다면
        return map[a][b];
    if(a == b)	// 숫자 1개짜리 팰린드롬의 경우
        return map[a][b] = true;
    if(a > b)	// 짝수개일때 서로 크로스 되는 경우 예외처리
        return true;
    if(nums[a] != nums[b])	//본격적 검사 1 - 외곽 값이 서로 같은지
        return map[a][b] = false;
    
    return map[a][b] = isF2(a+1,b-1);	//본격적 검사 2 - 내부가 팰린드롬인지
}

메모이제이션 여부를 먼저 확인하고,

종료조건인 숫자 1개, 크로스 경우(이건 예외처리라 저장하지 않는다) 를 먼저 확인한다음

펠린드롬 여부를 검사한다. 검사 항목은 2가지이고 AND이기때문에 하나씩 조건검사해도 됨

코드

//https://www.acmicpc.net/problem/10942
using namespace std;
#include <iostream>
#include <vector>

vector<vector<int>> map;    //1 : 펠린드롬, 0: 펠린드롬 아님, -1: 아직 기록되지 않음
vector<int> nums;

bool isF2(int a, int b)
{
    if(map[a][b] != -1)
        return map[a][b];
    if(a == b)
        return map[a][b] = true;
    if(a > b)
        return true;
    if(nums[a] != nums[b])
        return map[a][b] = false;
    
    return map[a][b] = isF2(a+1,b-1);
}

int main()
{
    int N; scanf("%d", &N);
    map.resize(N+1,vector<int>(N+1,-1)); 
    nums.resize(N+1);
    for(int i = 1; i <= N; i++)
        scanf("%d", &nums[i]);
    int M;  scanf("%d", &M);
    while(M--)
    {
        int a, b;   scanf("%d %d",&a,&b);
        printf("%d\n",isF2(a,b));
    }
}

기억할 점

다른 사람의 풀이