[Programmers]-땅따먹기

문제

코드

class Solution {
    int solution(int[][] land) {
        int answer = 0;

        int[][] memo = new int[land.length][land[0].length];

        answer = memoization(memo, land);

        return answer;
    }



    public int memoization(int[][] memo, int[][] land){
        int x = memo[0].length;
        int y = memo.length;
        for(int i=0;i<x;i++){//마지막줄
            memo[y-1][i]=land[y-1][i];
        }

        int max = 0;

        for(int i = y-2; i>=0;i--){//1,0
            for(int j=0;j<x;j++){//0,1,2,3
                max = 0;
                for(int k=0;k<x;k++){//0,1,2,3
                    if(j==k) continue;
                    if(max<memo[i+1][k]) max = memo[i+1][k];

                }
                memo[i][j] = max + land[i][j];
            }
        }
        for(int i=0;i<x;i++){//첫줄
            if(max<memo[0][i]) max = memo[0][i];
        }
        return max;
    }

}

코드 설명

맨아랫줄 에서 위로올라간다.

최대값을 저장하고 같은 열을 연속해 못밟게 조건을 준다.

그리고 아래행에서 최대값을 가져와서.

메모제이션 배열 = 최대값 + 현재 자리 점수 이다.

아래에서 위로 올라왔으니 맨윗줄에는 최대값을 찾아 최대값을 반환한다.

요약

• 메모이제이션을 이용하여 데이터를 저장해 놓는다.
• 10점 받아서 기분좋네.