[ Baekjoon - 11/01 ] - 10942번: 팰린드롬?

• 문제 링크 : https://www.acmicpc.net/problem/10942

10942번: 팰린드롬?

 

• 소요 시간 : 1시간

팰린드롬? 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초 (하단 참고)

256 MB

41063

11640

7930

29.352%

문제

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

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

각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, 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

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 자바는 2.5초, 파이썬은 1.5초
     • 메모리 : 256MB
   • 문제
     
     • 수열의 개수 N개(1≤N≤2,000), 질문의 개수 M개(1≤M≤1,000,000)
     • 수열이 주어질때, S부터 E까지의 수열이 펠린드롬인지 출력하는 문제
   • 이해
     • M의 개수를 백만정도로 준것을 보고 DP가 필수라고 생각했다.
2. 문제를 익숙한 용어로 재정의와 추상화
   • 이해는 어렵지 않아서 생략
3. 문제를 어떻게 해결할 것인가
   • 1st 접근 - DP로 접근하기위한 표 만들기)

   • 

   • M개가 백만개이므로 DP로 구현하기위해 표를 그려보았고 가로축은 시작포인터, 세로축은 끝포인터로 잡아서 각 S부터 E까지가 펠린드롬인지 T,F로 나타내며 규칙을 찾아보았다.
   • S가 가르키는 값과 E가 가르키는 값이 같지않으면 무조건 펠린드롬이 아니어서 F로 두고,
     그게 아니라면 글자수에 따라 분기점을 나눠야한다 생각했다.
   • 글자수가 한자리라면 무조건 펠린드롬이고
     두자리라면 두 글자가 같아야 펠린드롬이다.
   • 3자리 이상부터는 바로 판단하기가 어려우므로 사이 글자수로 판단해야하는데, 조금씩 줄여가며 펠린드롬인지 확인하고 T나 F를 두어야한다.
4. 위 계획을 검증
   • DP로 구현하기위해 규칙을 찾아본 것이므로 크게 검증이 필요없을거라 생각한다. 이미 검증이므로..
5. 계획 수행 (실제코드 작성)
   1. Java 11

      • import java.util.*;
        import java.io.*;
        
        public class Main {
            static int N,M;
            static int[] nums;
            static StringBuilder sb = new StringBuilder();
        
            public static void main(String[] args) throws IOException {
                //System.setIn(new FileInputStream("src/input.txt"));
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
                N = Integer.parseInt(br.readLine());
                nums = new int[N+1];
        
                boolean[][] dp = new boolean[N+1][N+1];
        
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int n=1; n<=N; n++) {
                    nums[n] = Integer.parseInt(st.nextToken());
                }
        
                setDp(N, nums, dp);
        
                M = Integer.parseInt(br.readLine());
                while (M-- > 0) {
                    st = new StringTokenizer(br.readLine());
                    int i = Integer.parseInt(st.nextToken());
                    int j = Integer.parseInt(st.nextToken());
                    sb.append(dp[i][j]?"1\n":"0\n");
                }
                System.out.print(sb);
            }
        
            private static void setDp(int N, int[] nums, boolean[][] dp) {
                for (int n=1; n<=N; n++) {
                    dp[n][n] = true;
                    if (nums[n] == nums[n-1]) {
                        dp[n-1][n] = true;
                    }
                }
        
                for (int i=2; i<N; i++) {
                    for (int j=1; j<=N-i; j++) {
                        if (nums[j] == nums[j+i] && dp[j+1][j+i-1]) {
                            dp[j][j+i] = true;
                        }
                    }
                }
            }
        }

   2. Python 3

      • import sys
        #sys.stdin = open("input.txt")
        input = sys.stdin.readline
        
        def setDp(N, nums, dp):
            for n in range(1,N+1):
                # 1자리 - 펠린드롬
                dp[n][n] = True
                # 2자리 - 같은수면 펠린드롬
                if nums[n] == nums[n-1]:
                    dp[n-1][n] = True
        
            # 3자리 이상이라면 앞뒤를 한글자씩 제외하며 펠린드롬인지 구하기
            for i in range(2,N):
                for j in range(1,N-i+1):
                    if nums[j] == nums[j+i] and dp[j+1][j+i-1]:
                        dp[j][j+i] = True
        
        if __name__ == '__main__':
            N = int(input())
            nums = [0]+list(map(int,input().split()))
        
            dp = [[False for _ in range(N+1)]for _ in range(N+1)]
        
            setDp(N,nums,dp)
        
            M = int(input())
            for _ in range(M):
                i,j = map(int,input().split())
                print(1 if dp[i][j] else 0)

 

• 결과