[C++로 풀이] 땅따먹기 (DP)⭐⭐

📌 땅따먹기

난이도 ⭐⭐

🚀 문제

🚀 내 풀이

✈ 1차 풀이 ❌

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

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

    vector<int> fourColRecord(4);

    int selectedIndex = 0;
    for (int i = 0; i < fourColRecord.size(); i++) {
        for (int j = 0; j < land.size(); j++) {
            if (j == 0) {
                fourColRecord[i] = land[0][i];
                selectedIndex = i;
            }
            else {
                int max = 0;
                int index = 0;
                for (int k = 0; k < 4; k++) {
                    if (k != selectedIndex && max <= land[j][k]) {
                        max = land[j][k];
                        index = k;
                    }
                }
                selectedIndex = index;
                fourColRecord[i] += max;
            }
        }
    }
    
    answer = *max_element(fourColRecord.begin(), fourColRecord.end());
    
    return answer;
}

위와 같이 풀어 장렬하게 틀렸다. 위 풀이는 첫 행에서 4열 중 어떤 열을 선택했느냐를 기준으로 선택한, 첫번째 행에서 출발한 열에 따라서 쭉 내려와 최대값을 구하는 식으로 시도했던 것이였다. 이렇게 풀면 안된다!

이 문제는 다이나믹 프로그래밍으로 풀면 된다는 힌트를 본 후 다이나믹 프로그래밍 다시 공부하고 아래와 같이 풀이. 다이나믹 프로그래밍 문제 앞으로 많이 풀어봐야할듯 싶다.

✈ 2차 풀이 (Dynamic Programming) ⭕

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

int solution(vector<vector<int>> land)
{
    int answer = 0;
    vector<vector<int>> dp(land.size(), vector<int>(4));
    
    for(int i = 0; i < 4; i++)
        dp[0][i] = land[0][i];
    
    for(int i = 1; i < land.size(); i++){
        for(int j = 0; j < 4; j++){
            int max = 0;
            for(int k = 0; k < 4; k++){
                if (k == j) continue;
                if (max < dp[i - 1][k])
                    max = dp[i - 1][k]; 
            }   
            dp[i][j] = land[i][j] + max;
        }
    }
    
    answer = *max_element(dp.back().begin(), dp.back().end());
    
    return answer;
}

• ✨점화식✨ (R[i][j]은 내려오면서 land[i][j]에 도달하는 데까지 가질 수 있는 최대값이라고 정의.)
  • R[0][j] = land[i][j]
    • i = 0 첫 행
    • 위에서 내려올게 없으므로 그 곳에 도달하는데까지 가질 수 있는 최대값은 그냥 자기 자신이다.)
  • R[i][j] = land[i][j] + Max(R[i-1][k])
    • 지금 이곳까지 내려오는데 가질 수 있는 최대값 = 지금 이곳의 값 + 이전행의 열까지 내려오는데 가질 수 있는 3 개의 최대값 중 최대갓
    • i = 1 ~ land.size()-1 두번째 행 ~ 마지막 행
    • Max(R[i-1][k]) 이전 행의 자리까지의 최대값
      • j != k 이어야 한다. (동일한 열에서 내려올 수 없음)
        • 즉, R[5][2] 를 구하려고 하고 있다면 R[5][2] = land[5][2] + Max(R[4][0] + R[4][1] + R[4][3]) 이 된다. (R[4][2]는 제외)

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기