Reenact

DP문제다. dp[i]를 i번째 글자까지 해석했을 때의 암호의 수라고 놓고 dp로 해결해주면 된다. 이 때 0으로 시작하는 암호는 무조건 틀린 경우라 제외해줘야 한다. 그 이후 두 번째 자리부터 보면서, 보는 자리가 0인 경우는 앞 자리를 봐서 그 앞자리와 묶어서 10이나 20이 될 수 있으면 오류가 아니지만, 아닌 경우는 에러라서 0을 출력하고 return한다. 보는 자리가 0이 아니라면 그걸 한자리 수로만 볼 수도 있고, 앞자리와 묶어서 하나의 알파벳으로 해석할 수도 있다. 두 가지 경우를 모두 더해주면 된다.

대칭인 것과 아닌 것을 나눠서 대칭이 아닌 것의 개수를 2로 나눈 다음에 대칭인 거에 더해서 출력해주면 된다.

이것도 전형적인 DP문제다. dp[i][j]를 i번째부터 j번째까지의 행렬을 곱했을 때의 최소 연산 횟수로 저장한다. 그리고 i번째부터 j번째까지의 행렬의 곱은 i번째랑 나머지, (i번째, i+1번째)와 나머지, ... , (나머지)와 j번째 행렬의 곱으로 나누어서 생각할 수 있다. 그럼 그 중 최소가 되는 것을 골라 업데이트해준다.

DP를 이용하여 해결할 수 있다. n번째에 눌러줘야하는 발판을 now라고 했을 때 n번째에 있을 수 있는 두 발의 상태는 (0, now), ... ,(4, now)이다. 그러면 (0, now)는 n-1번째에 (0, 1), ... , (0, 4) 중에서 0을 누르지 않은 발로 now를 눌러줘야 최소가 된다. 이런 식으로 (4, now)일 때까지의 힘의 최소를 계산해주면 DP로 풀 수 있다.

arr[i][j]가 i번째 수부터 j번째 수까지 부분수열에 대해 펠린드롬에 필요한 개수라고 정의하고 dp로 풀면 된다

DP문제라 점화식을 잘 세우면 어렵지 않게 풀린다.

가장 긴 부분수열의 시작점을 처음과 끝 각각 2가지에 대해 구한 다음에 합이 가장 긴 경우에서 1을 빼주면 된다!

아이디어는 조금 생각해보면 크게 어렵지 않다 전기줄의 도착점들을 시작점이 작은 순서에서 큰 순서대로 배열해준다. 거기서 가장 긴 증가하는 부분 수열을 구한 다음에 전체 전기줄 개수에서 빼주면 된다!