[프로그래머스] Lv.2 땅따먹기 (Java)

문제 링크

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

프로그래머스

 

💡 아이디어

0행부터 자신의 행 이전까지의 최대합을 구하면서 마지막 행까지 모든 열의 최대합을 구하려고 합니다.

 

예시로 설명하겠습니다.

1. 0행은 이전 행의 값이 없으므로 그대로 둡니다.

1	2	3	5
5	6	7	8
4	3	2	1

 

2. 1행은 이전 행 값에서 자신의 열을 제외한 값들 중 가장 큰값을 가져와 자신의 값과 합칩니다.

1행 0열 : [1,2,3,5] 에서 가장 큰 수인 5를 가져와 자신의 값과 합친다.

1행 1열 : [1,2,3,5] 에서 가장 큰 수인 5를 가져와 자신의 값과 합친다.

1행 2열 : [1,2,3,5] 에서 가장 큰 수인 5를 가져와 자신의 값과 합친다.

1행 3열 : [1,2,3,5] 에서 가장 큰 수인 3를 가져와 자신의 값과 합친다.

1	2	3	5
5 + 5 = 10	6 + 5 = 11	7 + 5 = 12	8 + 3 = 11
4	3	2	1

 

3. 2행도 이전 과정과 마찬가지로 이전 행에서 자신의 열을 제외한 가장 큰 값을 가져와 자신의 값과 합친다.

1	2	3	5
5	6	7	8
4 + 12 = 16	3 + 12 = 15	2 + 11 = 13	1 + 12 = 13

 

4. 마지막 행에서 가장 큰 값을 return합니다.

---

전체 코드

import java.util.*;
class Solution {
    int solution(int[][] land) {
        int answer = 0;

        int max=0; // 최고점
        for(int i=1;i<land.length;i++){
            for(int j=0;j<4;j++){
                int iMax=0; // (i-1)행에서 같은 열이 아닌 값 중에 가장 큰 값.
                
                if(j!=0) iMax=Math.max(iMax,land[i-1][0]);
                if(j!=1) iMax=Math.max(iMax,land[i-1][1]);
                if(j!=2) iMax=Math.max(iMax,land[i-1][2]);
                if(j!=3) iMax=Math.max(iMax,land[i-1][3]);
                
                land[i][j]+=iMax; // 자기자신의 값 + 이전 열의 가장 큰 값
                
                if(i==land.length-1 && land[i][j]>max) max=land[i][j];
            }
        }
        return max;
    }
}