프로그래머스 2023.10.29 (2Lv 땅따먹기)

프로그래머스

문제

---

문제 설명
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,
| 1 | 2 | 3 | 5 |
| 5 | 6 | 7 | 8 |
| 4 | 3 | 2 | 1 |
로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.
마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

제한사항
   ◈ 행의 개수 N : 100,000 이하의 자연수
   ◈ 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
   ◈ 점수 : 100 이하의 자연수

입출력 예

land	answer
[[1,2,3,5],[5,6,7,8],[4,3,2,1]]	16

코딩

---

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

int solution(vector<vector<int> > land)
{
    int answer = 0;

    for (size_t i = 1; i < land.size(); ++i)
    {
        int iland0 = land[i - 1][0];
        int iland1 = land[i - 1][1];
        int iland2 = land[i - 1][2];
        int iland3 = land[i - 1][3];

        land[i][0] += max(iland3, max(iland1, iland2));
        land[i][1] += max(iland3, max(iland0, iland2));
        land[i][2] += max(iland3, max(iland0, iland1));
        land[i][3] += max(iland2, max(iland0, iland1));
    }

    sort(land[land.size()-1].begin(), land[land.size()-1].end(), greater<int>());

    answer = land[land.size()-1][0];

    return answer;
}

레벨2 단계 문제를 어느정도 많이 풀어왔기 때문에 오늘은 스킬체크를 해보았다.

첫 문제로 해당 땅따먹기 문제가 나왔는데, 처음에는 문제를 깊게 생각하지 않아서 단순히 같은 열의 수끼리만 더해지지 않도록 다음행의 수들 중 가장 크면서, 열이 겹치지 않는 수들을 더해주었다.

주어진 예제는 문제 없이 통과하지만, 예외 상황이 너무 많아서 전체 실패가 떳다.

 

이후에 생각해낸 방법은 queue를 이용해 구해질 수 있는 경우의 수를 모두 구해, sort()를 이용해 오름차순으로 정렬한 뒤, 가장 첫번째 수를 제출했다. 이번에도 예제는 문제없이 통과했지만 역시 우려했던대로 시간 초과 문제로 실패 했다.

 

계속 고민하다가 생각이 안나서 찾아보니 이번 문제는 DP를 이용해 푸는 문제였다.

다른 알고리즘은 어느정도 공부해둬서 문제푸는데 어려움이 없었지만, DP는 공부하지 않아서 문제를 못풀었던 것 같다.

 

DP에 대해 더 공부를 하고, 문제를 많이 풀어봐야할 것 같다.

실행 결과

---