[Programmers] Lv2. 땅따먹기 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

입력으로 주어지는 배열 크기가 최대 \( 100,000 \times 4 \) 이기 때문에 DFS으로는 시간 초과가 걸릴 것 같더라구요. 유망하지 않은 부분은 가치지기를 하면 시간을 줄일 수 있겠지만, 기준을 어찌해야 할 지 모르겠었습니다. 그리디(Greedy)로도 현재 선택지가 최선의 선택지라는 보장이 없기에 못 사용하구요. 그래서 동적 프로그래밍(Dynamic Programming)을 한 번 사용해 봤습니다.

 

1. 땅(land)의 첫 행은 dp에 그대로 저장해둔다.
2. 현재 행과 열을 row, col이라고 할 때, dp[row - 1]에서 col을 제외한 최댓값을 찾아 newDpRow에 저장한다.
3. dp에 newDpRow를 추가한다.
4. 2, 3번 과정을 land의 마지막 행까지 반복한다.
5. 다 반복했다면, dp중에서 최댓값을 리턴한다.

 

동적 프로그래밍을 많이 사용해 본 적이 없어서, 코드를 작성해보는 데에 꽤나 애먹었습니다. DP 문제도 이제 좀 많이 풀어봐야겠네요. 아래는 제 소스 코드입니다.

 

✏️소스 코드 및 결과

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

int GetMaxValue(const vector<int>& row, int exceptColumn) {
    int maxValue = 0;
    for (int i = 0; i < row.size(); i++) {
        if (exceptColumn == i)
            continue;
        maxValue = max(maxValue, row[i]);
    }

    return maxValue;
}

int solution(vector<vector<int>> land)
{
    vector<vector<int>> dp(1, vector<int>(land[0].begin(), land[0].end()));

    for (int row = 1; row < land.size(); row++) {
        vector<int> dpRow;

        for (int col = 0; col < land[row].size(); col++) {
            int preDpRowMaxValue = GetMaxValue(dp[row - 1], col);
            dpRow.emplace_back(preDpRowMaxValue + land[row][col]);
        }

        dp.emplace_back(dpRow);
    }

    int lastRow = dp.size() - 1;
    return *max_element(dp[lastRow].begin(), dp[lastRow].end());
}

 

 

 

 

다른 분의 모범 코드 학습

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

int solution(vector<vector<int> > land)
{
    for(int i = 0; i < land.size() - 1; i++)
    {
        land[i + 1][0] += max(land[i][1], max(land[i][2], land[i][3]));
        land[i + 1][1] += max(land[i][0], max(land[i][2], land[i][3]));
        land[i + 1][2] += max(land[i][1], max(land[i][0], land[i][3]));
        land[i + 1][3] += max(land[i][1], max(land[i][2], land[i][0]));  
    }

    return *max_element(land[land.size() - 1].begin(), land[land.size() - 1].end());
}

• max(), min() 이런 함수들은 인자를 2개만 받을 수 있는 줄 알았는데, max({,1, 2, 3}) 이런 식으로 {  }를 통해 인자를 주게 되면 배열로 받아서 동작하나 봅니다. 나중에 유용하게 쓸 수 있을 것 같아요.
• 땅(land)의 이전 행은 볼 필요가 없으므로, 다음 행에다가 현재 행의 최댓값을 더해서 저장해두네요. 메모리를 별도로 안 써도 되니 굉장히 좋은 것 같습니다.