아이디어 시작점에서 임의의 i, j 까지 상승 비행 했을 때의 점수 + 임의의 i, j 에서 끝점까지 하강 비행 했을 때의 점수를 계산하고 모든 i, j 를 탐색하면서 그 값이 가장 큰 것을 출력하면 된다. 임의의 i, j 에서 끝점까지 하강 비행했을 때의 점수는 역으로 생각하면 끝점에서 임의의 i, j 까지 상승 비행 했을 때의 점수가 되므로 이를 활용해 문제를 해결하면 된다. ascending[i][j] = Math.max(ascending[i + 1][j], ascending[i][j - 1]) + score[i][j] descending[i][j] = Math.max(descending[i + 1][j], descending[i][j + 1]) + score[i][j] dp[i][j] = asce..

아이디어 지울 수 있는 문자열 중에 점수가 큰 것부터 지워나가면 되지 않을까 생각했지만 이런 그리디 방식의 탐색은 bab 2 bab 3 a 2 와 같은 사례에서는 통하지 않는다. 따라서 문자열 S 를 앞에서부터 탐색해가면서 지울 수 있는 문자열이 등장했을 때 이를 통으로 지우는 것 vs 단순히 문자 하나를 지우는 것 중 어떤 방법이 더 점수를 높게 가져갈 수 있는지를 확인하는 방식을 사용해야 한다. dp[i] 를 문자열 S 에 대해 i 번째 문자까지 탐색했을 때 최대 점수 라고 정의한다면 dp[i] = Math.max(dp[i - 1] + 1, dp[i - 지울 수 있는 문자열의 길이] + 지울 수 있는 문자열의 점수) 가 된다. 풀이코드 import java.io.BufferedReader; impor..