Today's Algorithm(2019-01-21)

programmers. 카드 게임

문제의 갈피를 잡지 못해 다른 사람의 코드를 참고하였습니다. 동적계획문제 라는 것이 그 느낌을 알기전엔 참 어떻게 해결해야 할지 알기가 힘든 것 같아요. 그래도 이번 문제를 통해 또 다시 쪼금(?!) 감을 잡을 수 있었습니다.

 

동적계획에서 dp배열을 만들때는 그것을 어떻게 정의하는지가 중요합니다. 이 문제 같은 경우 이와같이 정의할 수 있죠.

dp[i][j] = 왼쪽 i번째, 오른쪽 j번째일 때 최대값을 가진다

위와 같이 정의한다면 문제의 상황은 다음과 같이 해석할 수 있을 것입니다.

dp[i - 1][j - 1] = 양쪽 모두 버릴 때
dp[i - 1][j] = 왼쪽만 버릴 때
dp[i][j - 1] + right[j - 1] = 오른쪽만 버릴 때

 

처음보았을 때 이게 무슨 의미인지 깨닫기 어려웠습니다. 하지만 i와 j가 의미하는것이 무엇인지 정확히 알면 좀 더 쉽게 알 수 있습니다. i와 j는 왼쪽과 오른쪽에서 가리키는 번째를 의미합니다. 그리고 1base 입니다. 동적계획 문제에선 위와 같이 i - 1, j - 1되는 부분이 있기 때문에 i나 j가 0인 부분은 0으로 채워두고 하는 것이 편합니다.

 

다시 말하면 int[] right = {1, 2, 3, 4}; 이고 int[] left = {4, 1, 2, 3} 일 때 dp[2][3] 인 지점은 left가 2번째인 1, right가 3번째인 3을 의미합니다.

public class Solution {
        public int solution(int[] left, int[] right) {
            int[][] dp = new int[left.length + 1][right.length + 1];

            for (int i = 1; i <= left.length; i++) {
                for (int j = 1; j <= right.length; j++) {
                    dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]);
                    if(left[i - 1] > right[j - 1]) {
                        dp[i][j] = Math.max(dp[i][j], dp[i][j - 1] + right[j - 1]);
                    }
                }
            }

            int answer = 0;
            for (int i = 1; i <= right.length; i++) {
                answer = Math.max(answer, dp[left.length][i]);
            }
            return answer;
        }
}