[java/python] 프로그래머스 Lv.2 - 땅따먹기

코딩테스트 연습 - 땅따먹기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

dp를 사용하여 해결하였다.

 

[python]

def solution(land):
    if len(land) == 1:
        return max(land)
    else:
        for i in range(1,len(land)):
            for j in range(4):
                if j == 0:
                    land[i][j] += max(land[i-1][1], land[i-1][2], land[i-1][3])
                elif j ==1:
                    land[i][j] += max(land[i-1][0], land[i-1][2], land[i-1][3])
                elif j ==2:
                    land[i][j] += max(land[i-1][0], land[i-1][1], land[i-1][3])
                else:
                    land[i][j] += max(land[i-1][1], land[i-1][2], land[i-1][0])
        return max(land[-1])

처음에 테스트케이스를 통과하였으나 온통 실패로 떴는데

dp 배열을 만들어놓고 max 값을 더해나가는 식으로 풀었더니 오류가 났다.

더해진 후의 인덱스를 고려하는 것이 아니라 처음 인덱스가 기준이 되었기 때문이다.

그래서 그냥 2차원 배열의 인덱스 1부터 시작하여 아예 원소의 값을 바꾸는 식으로 수정하였더니 해결되었다.

 

 

 

[java]

class Solution {
    int solution(int[][] land) {
        int answer = 0;
        for(int i=1;i<land.length;i++){
            land[i][0] += Math.max(land[i-1][1], Math.max(land[i-1][2], land[i-1][3]));
            land[i][1] += Math.max(land[i-1][0], Math.max(land[i-1][2], land[i-1][3]));
            land[i][2] += Math.max(land[i-1][0], Math.max(land[i-1][1], land[i-1][3]));
            land[i][3] += Math.max(land[i-1][0], Math.max(land[i-1][1], land[i-1][2]));
        }
        
        for(int i=0; i<4; i++){
            answer = Math.max(answer, land[land.length-1][i]);
        }
        return answer;
    }
}