[프로그래머스 4단계] 알고리즘 37. 땅따먹기 게임

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)

알고리즘 37. 땅따먹기 게임

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

#include<iostream>

#include<vector>

using namespace std;

int hopscotch(vector<vector<int> > board)

{

    // 함수를 완성하세요.

    int answer = 0;

    return 0;

}

int main()

{

    vector<vector<int> > test{{1,2,3,5},{5,6,7,8},{4,3,2,1}};

//아래는 테스트로 출력해 보기 위한 코드입니다.

    cout << hopscotch(test);

}

풀이: 

우선 내가 짠 알고리즘은 다음과 같다.

1. 첫줄에서 가장 큰 땅을 찾는다.
2. 다음 줄에서 가장 큰 땅을 찾되 이전 먹은 땅과 열이 겹치지 않도록 먹는다.
3. 합계를 합산한다.

알고리즘에 따라 계산하면 다음과 같다.

int hopscotch(vector<vector<int> > board)

{

    // 함수를 완성하세요.

    int answer = 0;

int pre_pos = -1;

for (int i=0; i<board.size(); i++)

{

int max_pos = 0;

for (int j=0; j<board[i].size(); j++)

{

if (pre_pos == j)

continue;

if (board[i][max_pos] < board[i][j])

max_pos = j;

}

answer += board[i][max_pos];

pre_pos = max_pos;

}

    return answer;

}

이전 먹은 땅을 기억해 겹치지 않도록 만든 것이다. 그런데 이러면 엄청난 큰 오류를 범한다. 만약 

1      2 3 5
5      6 7 8
4      3 2 1

1000 0 9 8

이런 테이블일 때 내가 만든 알고리즘을 대입해보면 5 + 7 + 4 + 9 가 되어버린다. 이는 5 + 7 + 3 +1000 보다 낮은 수가 되어버린다. 즉 위 알고리즘은 틀렸다. 다시 알고리즘을 생각해보자. 이번에는 모든 위치에서 나올 수 있는 모든 수를 더하는 방식으로 해결할 것이다. 열은 4열이라는 것을 기억하자.

1. 다음을 반복한다.
• 다음 칸 첫번째 열을 선택할 경우 이전의 2, 3, 4 열의 최대를 선택해야 한다.
• 다음 칸 두번째 열을 선택할 경우 이전의 1, 3, 4 열의 최대를 선택해야 한다.
• 다음 칸 세번째 열을 선택할 경우 이전의 1, 2, 4 열의 최대를 선택해야 한다.
• 다음 칸 네번째 열을 선택할 경우 이전의 1, 2, 3 열의 최대를 선택해야 한다.
2. 이를 마지막 행까지 반복해서 더해준 후 최대를 뽑는다.

이렇게 해서 4열에서 선택될 수 있는 가지의 경우수를 구한다. 코드는 다음과 같다.

int hopscotch(vector<vector<int> > board)

{

    // 함수를 완성하세요.

    int answer = 0;

int N = board.size();

for (int i=0; i<N-1; i++)

{

board[i+1][0] += get_max( {board[i][1], board[i][2], board[i][3]} );

board[i+1][1] += get_max( {board[i][0], board[i][2], board[i][3]} );

board[i+1][2] += get_max( {board[i][0], board[i][1], board[i][3]} );

board[i+1][3] += get_max( {board[i][0], board[i][1], board[i][2]} );

}

answer = get_max ( board[N-1] );

return answer;

}

예제를 들어서 확인해보자.

1 2 3 5
5 6 7 8
4 3 2 1

->

1   2   3  5

10 11 12 11

16 15 13 13

-> 최대값 16

이렇게 해서 구할 수 있다. 그럼 이전에 알고리즘에서 실패했던 예도 살펴보자.

1      2 3 5
5      6 7 8
4      3 2 1

1000 0 9 8

-> 

1      2  3   5

10    11 12 11

16    15 13 13

1015 16 25 24

-> 최대값은 1015

코드를 보면 직관적이라 이해가 쉬울 것이다.  이렇게 해서 4단계 문제도 모두 풀었다. 이제 얼마 안남았다 파이팅!