[백준] [DP] 10942번 팰린드롬? 문제

개발/백준_알고리즘2016. 11. 14. 22:55

뷰어
댓글로
이전글
다음글

문제

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

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	2995	858	566	32.907%

문제

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

먼저, 홍준이는 자연수 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을 출력한다.

예제 입력

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

예제 출력

코드 설명)

1) num[] 자연수 N

2) ppap[s][e] s~e 사이가 펠린드롬이면 1 아니면 0

(1)처음에 ppap[0][0], [0][1], [1][0], [1][1] 1로 초기화

그리고 자기 자신은 [1][1], [2][2], ~ ... 펠린드롬이니 1로 초기화

ppap[i+1][i] = 1 로 초기화 해주는 이유는 예를 들어 num[1] =1, num[2] =1, num[3] =1 일때 [1] == [2] 같을때 비교문이 ppap[2][1] 을 가르키게 된다 ([2]==[3] 일경우 [3][2]를 가르킴) 그렇기 때문에 초기값을 1로 넣어줘야한다.

* 제 소스만 해당하는 특별한 경우입니다 :(...

(2) for문에서 ( for(int i = 1; i <= n - 1; i++) ) i는 거리를 나타냅니다.

예를 들어 12321 이있다고 하면

예) [1][2][3][2][1] 에서 i가 1일 경우 [1][2][3][2][1], [1][2][3][2][1], [1][2][3][2][1] ... 이고

i가 2일 경우 [1][2][3][2][1], [1][2][3][2][1], [1][2][3][2][1]

배열 사이의 거리를 의미한다고 생각하시면 됩니다.

다음 for문(for(int j = 1; j <= n - i; j++))는 배열 값의 최대를 넘지 않고 비교 하기 위한 위치를 나타내는 포문 입니다.

예를 들어 위의 예시 i 가 1일 때 [1][2][3][2][1], [1][2][3][2][1], [1][2][3][2][1] ...

파란색을 의미 하는 포문 입니다.

if문은 가르키는 위치가 서로 같은지 비교를 해주고 그 사이 값이 팰린드롬 인지 확인합니다.

이해하면 생각보다 쉬운데 소스가 생각보다 깔끔히 짜진 못했네요..

#include <iostream>
#include <cstdio>
 
int num[2001];
int ppap[2002][2002];
 
int main(){
    
    int n;
    // std::cin >> n;
    scanf("%d", &n);
 
    for(int i = 1 ; i <= n ; i++)
        scanf("%d", &num[i]);
        // std::cin >> num[i];
 
 
    int n2;
    scanf("%d", &n2);
    // std::cin >> n2;
 
    //init
    ppap[0][0] = 1;
    ppap[0][1] = 1;
    ppap[1][0] = 1;
 
    for(int i = 1; i <= n ; i++){
        ppap[i][i] = 1;    // self
        ppap[i+1][i] = 1;        // for the 1 block can be "1" ex) 1~2, 2~3
    }
 
    // distance
    for(int i = 1; i <= n - 1; i++)
        for(int j = 1; j <= n - i; j++)
            if( num[j] == num[j + i] && ppap[j + 1][j + i - 1] == 1)
                ppap[j][j+i] = 1;
 
    while (n2--){
        int S, E;
        scanf("%d %d", &S, &E);
        printf("%d\n", ppap[S][E]);
 
        // cin 으로 하면 시간 초과
        // int S, E;
        // std::cin >> S >> E;
        // std::cout << ppap[S][E] << std::endl;
    }
 
    return -1;
}

Colored by Color Scripter

'개발 > 백준_알고리즘' 카테고리의 다른 글

[백준] [DP] 2293번 동전 1 (1)	2016.11.16
[백준] 1254번 팰린드롬 만들기 (0)	2016.11.13
[백준][DP] 2294번 : 동전 2 문제 (0)	2016.11.08

죠노이 노트