<Programmers> 땅따먹기

[내 코드]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
public static void main(String[] args) {
int[][] land = {{1, 2, 3, 5},
{5, 6, 7, 8},
{4, 3, 2, 1}};
int answer = 0;
int rNum = -1;
int max = 0;
for (int i = 0; i < land.length; i++) {
if (rNum == -1) {
for (int j = 0; j < 4; j++) {
if (max < land[i][j]) {
max = land[i][j];
rNum = j;
}
}
answer += max;
max = 0;
} else {
row(land, rNum);
for (int j = 0; j < 4; j++) {
if (max < land[i][j]) {
max = land[i][j];
rNum = j;
}
}
}
answer += max;
max = 0;
}
}

static void row(int[][] land, int rNum) {
for (int i = 0; i < land.length; i++) {
for (int j = 0; j < 4; j++) {
if (j == rNum) {
land[i][j] = 0;
}
}
}
}
}

 

내 코드로 작성하니 테스트 케이스만 통과하고 테스트는 전부 실패하였다. 블로그를 참고하니 DP를 이용하여 풀이하는 것이 바람직하다.

https://zzang9ha.tistory.com/38

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

 

[보완된 코드]

import java.util.*;

class Solution {
public static int solution(int[][] land) {

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][1], Math.max(land[i-1][0], 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<land.length; i++){
            Arrays.sort(land[i]);
        }
        return land[land.length-1][3];
    }
}