땅따먹기 게임

문제

영희는 땅따먹기 게임에 푹 빠졌습니다. 땅따먹기 게임의 땅은 총 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		2		3		5
5		6		7		8
10		11		1000	12

단순하게 짰더니 1000이라는 큰 값을 결과적으로 체크도 안하고 넘어간다.

따라서 생각해본게 결국 탐색은 전부 다 하자였다.

#include <iostream>
#include <vector>
using namespace std;

int hopscotch(vector<vector<int> > board)
{
  int answer = 0;

  for (int i = 1; i < board.size(); i++)
  {
    for (int j = 0; j < 4; j++, answer = 0)
    {
      for (int k = 0; k < 4; k++)
      {
        if (j != k)
          answer = (answer > board[i - 1][k]) ? answer : board[i - 1][k];
      }
      board[i][j] += answer;
    }
  }

  for (int i = 0; i < 4; i++)
    answer = (answer > board[board.size() - 1][i]) ? answer : board[board.size() - 1][i];

  return answer;
}

int main()
{
  vector<vector<int> > test{ { 1, 2, 3, 5 }, { 5, 6, 7, 8 }, { 4, 3, 2, 1 } };
  // 아래는 테스트로 출력해 보기 위한 코드입니다.
  cout << hopscotch(test);
}

현재 row을 기준으로(i) j, 즉 0,1,2,3 인덱스의 경우의 수를 모두 따져본다.

예를 들어 n번라인, 2번 라인이라 가정해보면 여기서 (5,6,7,8)에서 선택될 수가 4가지다. 하지만 n+1, 즉 다음 라인에서 선택될 수는 3가지다. 이전 인덱스랑 동일한건 빼야되니까.

따라서 각각의 수에 대해서 가질 수 있는 최고의 수를 라인에 기록한다.

예를 들어 그 전 라인에서 어떤 조건을 통해서 5를 선택했다면 다음 가질 수 있는 수는 최대 1005이다. 같은 방법으로 6을 선택했으면 1006이겠고 8은 1008이다.

하지만 7을 선택했다면 가질 수 있는 최대의 수는 19이다. 따라서 우리는 이 전 수에서 8을 선택했을 때 최고의 계산 값이 나옴을 알 수 있다.

어차피 인덱스는 j != k에서 같은 인덱스가 걸릴 일은 없다. 임의로 행렬을 작성해서 동그라미, 세모, 네모, 별표를 가지고 각각의 루트를 계산해보면 이해하기 한결 쉬울 것이다. (저도 그렇게 했어요)

출처

알고리즘 연습 Level 4 | 프로그래머스