Easy is Perfect

[백준] 10942번 C/C++ 풀이 _ 팰린드롬

  • melonicedlatte
  • Sep 26, 2018


출처 : https://www.acmicpc.net/problem/10942 

팰린드롬?

시간 제한메모리 제한제출정답맞은 사람정답 비율
0.5 초256 MB111123297198929.905%

문제

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.

각 질문은 두 정수 S와 E로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.

예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.

  • S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
  • S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
  • S = 3, E = 3인 경우 1은 팰린드롬이다.
  • S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.

자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

출력

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

예제 입력 1 

7
1 2 1 3 1 2 1
4
1 3
2 5
3 3
5 7

예제 출력 1 

1
0
1
1

출처

알고리즘 분류

풀이

팰린드롬을 갱신하는 가장 간단한 방법은 무엇일까요?

먼저, start ~ end 까지가 팰린드롬인지 확인하고 싶다고 가정해봅니다. 
is_palindrome[start][end] 의 값을 갱신해야 하는 상황입니다. 

이 상황에서 팰린드롬인지 확인하는 방법은 is_palindrome[start+1][end-1]인 부분이 팰린드롬이면서, 
start 와 end 의 숫자가 서로 같으면 팰린드롬이 됩니다. 

처음에 start와 end 가 같거나 1만큼 차이가 나면 초기화가 필요합니다.
나머지 부분은 위의 논리를 이용하여 모든 배열을 갱신시켜주면 됩니다. 

아래의 소스코드를 확인해주세요. 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <algorithm>
using namespace std; 
#pragma warning(disable:4996)
#define NMAX 2000 + 1 
int main() {
    int N, M; int num[NMAX] = { 0 }; int is_palindrome[NMAX][NMAX] = { 0 };
    scanf("%d", &N);
    for (int n_idx = 1; n_idx <= N; n_idx++) 
        scanf("%d", &num[n_idx]);
  // 초기화
    int gap = 0; 
    for (int start_idx = 1; start_idx + gap <= N; start_idx++) {
        int end_idx = start_idx + gap;
        is_palindrome[start_idx][end_idx] = 1;
    }
    gap = 1;
    for (int start_idx = 1; start_idx + gap <= N; start_idx++) {
        int end_idx = start_idx + gap; 
        if (num[start_idx] == num[end_idx]) 
            is_palindrome[start_idx][end_idx] = 1;
    }
    // 팰린드롬은 양 끝이 달라지는 것이기 때문에
    // start_idx 와 end_idx를 각각 +1,-1을 한 것이 팰린드롬이고, 양끝이 같으면 == 팰린드롬 
    // start_idx 와 end_idx를 각각 +1,-1을 한 것이 팰린드롬이 아니거나, 양끝이 다르면 != 팰린드롬
    for (gap = 2; gap <= N; gap ++) {
        for (int start_idx = 1; start_idx + gap <= N; start_idx++) {
            int end_idx = start_idx + gap;
            if (is_palindrome[start_idx + 1][end_idx - 1] && num[start_idx] == num[end_idx])
                is_palindrome[start_idx][end_idx] = 1;
        }
    }
    scanf("%d", &M);
    while (M--) {
        int start, end; scanf("%d %d", &start, &end);
        printf("%d\n", is_palindrome[start][end]);
    }
    return 0;
}
cs



Search