[프로그래머스] 땅따먹기/Java

문제

https://programmers.co.kr/learn/courses/30/lessons/12913

코딩테스트 연습 - 땅따먹기

풀이

각 행을 레벨이라고 치자. land[i][j]의 값 의미는 i레벨까지 왔고 마지막 열이 j열 일 때 최댓값이다.

예를들어 land[1][0]은 1레벨까지 왔고 마지막 열이 0일 때 최댓값을 담고 있다. 

그럼 그러한 최댓값은 어떻게 구할까?

land[i][0]의 최댓값은 직전 레벨까지왔고 마지막 열이 1, 2, 3인 값중 가장 큰 값과  i레벨 0열의 값을 더한 값이다.

따라서 밑에 코드처럼 작성할 수 있다.

 

마지막엔 결국 0,1,2,3열로 끝나는 4개의 최댓값이 나온다. 이 최댓값 중 가장 큰 값을 반환하면된다. 

주의할 점

딱히 없다.

코드

package 프로그래머스.레벨2.땅따먹기.첫풀이;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

public class Solution {

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

        for (int i=0; i<4; i++) {
            answer = Math.max(answer, land[numOfRow-1][i]);
        }

        return answer;
    }

    @Test
    void test() {
        Assertions.assertEquals(16, solution(new int[][]{{1,2,3,5},
                {5,6,7,8},
                {4,3,2,1}}));
    }
}