땅따먹기

문제

---

문제 풀이

처음에는 예시를 보고 같은 열에 있지 않고 높은 수만 골라서 가면 되지 않나 싶어서 2중 배열로 맥스값을 찾으면 넘어 가는 방식으로 처리 했다가 테스트에서 모두 틀리는 현상을 얻어 맞았다. 

 

문제를 잘 못 이해 한 듯 해서 질문게시판으로 가니 역시나 문제 자체를 잘 못 이해하고 있었다. 

아래 2행짜리가 있다고 보자. 여기서 어떤 방법이 가장 높은 점수를 얻는 루트인가 보면 4 -> 20을 밟았을때가 최고점이다. 

 

{1, 2, 3, 4, 5}

{1, 1, 1, 1, 20}

 

이러한 방식으로 dp 로 처리한 문제이다. 

---

나의 답안

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

dp[0] = land[0].clone();

for (int i = 1; i < land.length; i++) {
    for (int j = 0; j < land[0].length; j++) {
        for (int k = 0; k < land[0].length; k++) {
            if (j == k) continue;
            dp[i][j] = Math.max(dp[i][j], dp[i - 1][k] + land[i][j]);
        }
    }
}

return Arrays.stream(dp[land.length-1]).max().orElse(0);