프로그래머스 lv2 땅따먹기

문제 링크

땅따먹기

풀이

처음에는 for문을 하나하나 써서 Top-Down으로 만들어 보고 그걸 그대로 재귀로 풀었다. 그러나 재귀의 결말은 늘 시간초과거나 뭐 그렇다.

이 문제를 어떻게 풀어야 할지 고민하다가 다른 분이 풀어놓으신 걸 보고 풀어낼 수 있었다.

방법은 주어진 배열을 한번 씩 내려가면서, 거기까지 내려갔을때의 최대값을 저장하는 것이다.

주어진 배열은 다음과 같다.

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |    

이 배열을 이전 행의 최대값을 하나씩 더해준다고 생각해보자.

| 1 | 2 | 3 | 5 |

| 10 | 11 | 12 | 11 |

| 16 | 15 | 13 | 13 |

그럼 위와 같은 배열이 나온다.

조금 더 자세하게 설명하면,

5 (land[1][0]) 에 윗줄의 최대값, 즉 같은 열이 아닌 값들 중에서 최대값을 구해서 더해준다고 생각해보자.

그러면 윗 행인 [1, 2, 3, 5] 중에가 같은 열이 아닌 1을 제외하고, 최대값인 5를 더해준다.

그러면 land[1][0]까지 오는 길의 가장 최대값을 구할 수 있다.

이렇게 생각해서 아래열까지 쭉쭉 내려간다면?

마지막 행에는 결국 해당 위치까지 가는데 최대값을 구할 수 있다.

위의 풀이 방식을 코드로 바꾸면 다음과 같이 구현된다.

import java.util.Arrays;
import java.util.stream.IntStream;

class Solution {
    public int solution(int[][] land) {
        IntStream.range(1, land.length).forEach(i -> {
            land[i][0] += max(land[i - 1][1], land[i - 1][2], land[i - 1][3]);
            land[i][1] += max(land[i - 1][0], land[i - 1][2], land[i - 1][3]);
            land[i][2] += max(land[i - 1][0], land[i - 1][1], land[i - 1][3]);
            land[i][3] += max(land[i - 1][0], land[i - 1][1], land[i - 1][2]);
        });

        return max(land[land.length - 1]);
    }

    private int max(int a, int b, int c) {
        return Math.max(a, Math.max(b, c));
    }

    private int max(int[] arr) {
        return Arrays.stream(arr).max().getAsInt();
    }
}