DP37 백준 10942 / C++ https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net [ 풀이 ] 어떤 문자열이 팰린드롬이라면 양쪽으로 1개씩 옮겨가면서 조사해줄 수 있다. 즉, 이전 상태를 다시 활용할 수 있으므로 메모이제이션이 가능한 문제다. dp[i][j]:= 구간[i,j]가 팰린드롬이면 1, 아니면 0을 의미한다고 하자. 이제 [i-1, j+1]로 이동한다면.. a[i-1]=a[j+1]이고 dp[i][j]=1일때만 dp[i-1][j+1]도 1이 된다. 비트연산으로 간단히 하면 dp[i-1][j+1]=dp[i][j.. 2022. 7. 21. 이전 1 ··· 7 8 9 10 다음