[BOJ 10942] 팰린드롬?
> 문제 출처 https://www.acmicpc.net/problem/10942 > 문제 설명 N개(1 ≤ N ≤ 2,000)의 자연수(K ≤ 100,000)로 이루어진 수열이 주어졌을 때, M개의 구간(M≤ 1,000,000)을 입력받는다. 이 때 입력받은 각각의 구간이 팰린드롬이면 1, 팰린드롬이 아니면 0을 출력한다. > 접근 방법 질문의 개수(M)이 최대 1,000,000개이기 때문에 모든 상황에서의 dp값을 구한 후 리턴하는것이 효율적이라 생각했다. 그래서 수열의 값을 입력받으면서 모든 sub-problem을 계산했다. i번째 값을 입력받으면 dp[i-1][i], dp[i-2][i], ... dp[1][i]를 계산하는 방식으로 설계했으며, 총 시간복잡도는 O(N^2)이라고 생각된다. 점화식(a..
2020. 9. 2.
