문제풀이/백준

[C++] 백준 - 10942 : 팰린드롬?

orubt 2021. 1. 13. 20:18
반응형

문제 링크

 

10942번: 팰린드롬?

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

www.acmicpc.net

 

풀이 )

  M이 1,000,000 이하이므로 cin으로 입력을 받을 시 cin.tie(null), ios::sync_with_stdio(false) 처리를 해주어야 한다.

  또 각 경우에 대해서 O(n^2)인 경우 시간 초과가 발생하게 되므로 해결하기 위해 DP를 이용했다.

 

  먼저 dp 배열의 행과 열은 각각 시작, 끝을 의미한다.

  dp 배열의 모든 원소 값을 -1로 초기화 시킨다.

 

  check( )는 시작 s와 끝 e에 대해서

  • dp[s][e]가 갱신된 적이 있다면(dp[s][e] != -1), 즉 팰린드롬 여부가 결정된 경우 바로 결과를 반환한다.
  • e == s인 경우 즉 글자 하나인 경우 팰린드롬이므로 dp[s][e]를 갱신하고 true 반환
  • e < s 인 경우가 오는 경우는 피호출함수에서 매개변수간 차가 1인 경우 예를 들어 check(1, 2)와 같은 경우 뿐이다.
    함수가 호출되기 위해서는 arr[1]와 arr[2]가 같아야 하기 때문에 길이가 2이고, 두 문자가 같다는 의미이다
    따라서 dp[s][e]를 갱신하고 true 반환
  • 양쪽 끝 문자가 다른 경우 팰린드롬이 아니므로 dp[s][e]를 갱신하고 false 반환
  • 양쪽 끝 문자가 같은 경우 양쪽에서 한칸씩 당기면서 팰린드롬인지 여부 확인

 

#include <iostream>

using namespace std;

int arr[2000];
int dp[2000][2000];

bool check(int s, int e){
    if(dp[s][e] != -1)
        return dp[s][e];

    if(e <= s)
        return dp[s][e] = true;

    if(arr[s] != arr[e])
        return dp[s][e] = false;

    return dp[s][e] = check(s+1, e-1);
}

int main(void){
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n, m;

    for(int i = 0; i < 2000; ++i)
        for(int j = 0; j < 2000; ++j)
            dp[i][j] = -1;

    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> arr[i];

    cin >> m;
    while(m--){
        int s, e;
        cin >> s >> e;
        cout << check(s-1, e-1) << '\n';
    }
    return 0;
}
반응형