109421 [C/C++] 백준 10942: 팰린드롬? (DP) https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이? 먼저 펠린드롬이란 거꾸로 읽어도 제대로 읽는 것과 같은 문장을 뜻한다. 이 문제에서는 각 질문에 대하여 팰린드롬인지 아닌지를 답해야 하는데 질문의 개수가 10^6이고 수열의 크기가 최대 2000이기 때문에 사실상 각 질문마다 팰린드롬인지 확인을 한다면 시간복잡도가 O(NM)이 되기 떄문에 시간안에 풀 수 없다. 그렇기 때문에 각 수가 팰린드롬인지 아닌지를 새로운 배열에 저장해가며 풀어야만 시간 내의 해결이 가능하다. 다만 각 질.. 2023. 10. 21. 이전 1 다음
