Level 4- 땅따먹기 게임

영희는 땅따먹기 게임에 푹 빠졌습니다. 땅따먹기 게임의 땅은 총 N행 4열로 나누어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 땅을 밟으면서 한 행씩 내려올 때, 영희는 각 행의 4칸 중 1칸만 밟으면서 내려올 수 있습니다. 땅따먹기 게임에는 같은 열을 연속해서 밟을 수가 없는 특수 규칙이 있습니다. 즉, 1행에서 (5)를 밟았다면, 2행의 (8)은 밟을 수가 없게 됩니다. 마지막 행까지 모두 내려왔을 때, 점수가 가장 높은 사람이 게임의 승자가 됩니다. 여러분이 hopscotch 함수를 제작하여 영희가 최대 몇 점을 얻을 수 있는지 알려주세요. 예를 들어
1 2 3 5
5 6 7 8
4 3 2 1
의 땅이 있다면, 영희는 각 줄에서 (5), (7), (4) 땅을 밟아 16점을 최고점으로 받을 수 있으며, hopscotch 함수에서는 16을 반환해주면 됩니다.

풀이

처음에는 좀 단순하게 생각해서 각 배열의 가장 큰 숫자를 뽑고, 해당 index를 다음 배열에서 고를 수 없는 정도로만 생각했다.

int result = 0;
int priorIndex = 0;
for (int i = 0; i < size; i++) {
    int max = Integer.MIN_VALUE;
    int tempIndex = 0;
    for (int j = 0; j < board[i].length; j++) {
        if (i > 0 && j == priorIndex) continue;
        int temp = max;
        max = Math.max(temp, board[i][j]);
        if (temp != max) {
            tempIndex = j;
        }
    }
    priorIndex = tempIndex;
    result += max;
}

이랬는데 실제 프로그래머스에서 돌려보고 failed가 떠서 왜 그런가 생각해봤더니...

예시로 들어보면

1 3 5 4

2 1 9 8

1 2 3 100

이렇게 되어있을 때 내가 풀이한 방식으로 하면

5

8

3

을 골라 16이 될 것이다

이렇게 할 경우 2행 3열에 있는 100을 날려버리는 어처구니 없는 결과가 나오게 된다 ㅠ

이부분은 고민을 하다가 좀 답답해서 어쩔? 수 없이 구글링을 해봤는데

직관적으로 풀이한게 좋아서 올려보고자 한다.

Math.max를 통해서 각 배열의 합을 계속 비교함으로 구해주는 방식

class Hopscotch {
    int hopscotch(int[][] board, int size) {
        int result = 0;
        // 함수를 완성하세요.
        for (int i = 0; i < size - 1; i++) {
            board[i + 1][0] += Math.max(board[i][1], Math.max(board[i][2], board[i][3]));
            board[i + 1][1] += Math.max(board[i][0], Math.max(board[i][2], board[i][3]));
            board[i + 1][2] += Math.max(board[i][0], Math.max(board[i][1], board[i][3]));
            board[i + 1][3] += Math.max(board[i][0], Math.max(board[i][1], board[i][2]));
        }
        result = Math.max(board[size-1][0], Math.max(board[size-1][1], Math.max(board[size-1][2], board[size-1][3])));
        return result;
    }

    public static void main(String[] args) {
        Hopscotch c = new Hopscotch();
        int[][] test = { { 1, 2, 3, 5 }, { 5, 6, 7, 8 }, { 4, 3, 2, 1 } };
        //아래는 테스트로 출력해 보기 위한 코드입니다.
        System.out.println(c.hopscotch(test, 3));
    }

}

class Hopscotch { int hopscotch(int[][] board, int size) { return hopscotch(board, size, 0, -1); } private int hopscotch(int[][] board, int size, int y, int idx) { if (y >= size) return 0; int answer = Integer.MIN_VALUE; for (int i = 0; i < 4; i++) { if (i != idx) { answer = Math.max(hopscotch(board, size, y + 1, i) + board[y][i], answer); } } return answer; } public static void main(String[] args) { Hopscotch c = new Hopscotch(); int[][] test = { { 1, 2, 3, 5 }, { 5, 6, 7, 8 }, { 4, 3, 2, 1 } }; //아래는 테스트로 출력해 보기 위한 코드입니다. System.out.println(c.hopscotch(test, 3)); } }