문제

영희는 땅따먹기 게임에 푹 빠졌습니다. 땅따먹기 게임의 땅은 총 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을 반환해주면 됩니다.

풀이 1

class Hopscotch {
  int hopscotch(int[][] board, int size) {
    int result = 0;
    int sum = 0;	

    // 함수를 완성하세요.
    for (int i = 1; i < size; ++i){
      board[i][0] += Math.max(board[i-1][1], Math.max(board[i-1][2], board[i-1][3]));
      board[i][1] += Math.max(board[i-1][0], Math.max(board[i-1][2], board[i-1][3]));
      board[i][2] += Math.max(board[i-1][0], Math.max(board[i-1][1], board[i-1][3]));
      board[i][3] += Math.max(board[i-1][0], Math.max(board[i-1][1], board[i-1][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));
  }
}

노가다해서 하나하나 값 비교하여 코드 짜서 제출하고 보니 Math.max로 비교하여 깔끔하게 짠 소스가 있더라… 본질은 다르지 않아서 이 소스로 다시 바꾸었다.

시작은 1행부터 한다. 그래야 이전 행에서 자신의 인덱스와 같은 값을 제외한 값들 중에 제일 큰 값을 뽑아서 더할 수 있기 때문이다. 그리고 그 가장 큰 값을 현재 계산 중인 행에 더해준다. 이것을 반복하면 마지막 행의 각 열에는 행마다 자신의 인덱스와 겹치지 않는 가장 큰 값을 더해온 결과가 저장된다. 마지막으로 그 4개 값 중에 제일 큰 값을 다시 Math.max로 뽑아주면 된다.

풀이 2

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));
    }

}

재귀함수를 이용하여 깔끔하게 푼 풀이이다.