[프로그래머스] 땅따먹기 - DP

문제

 

풀이

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

// DP : 동적계산법
// 한번씩 내려가면서 최고의 합을 기억하며 내려오기

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

 

한 행씩 내려오면서 최고의 합을 기억한다.

 

| 4 | 3 | 2 | 1 | 

| 2 | 2 | 2 | 1 | 

| 6 | 6 | 6 | 4 | 

| 8 | 7 | 6 | 5 | 

 

| 4 | 3 | 2 | 1 |

| 5 | 6 | 6 | 5 | 

| 6 | 6 | 6 | 4 |

| 8 | 7 | 6 | 5 | 

 

| 4 | 3 | 2 | 1 |

| 5 | 6 | 6 | 5 | 

| 12 | 12 | 12 | 10 | 

| 8 | 7 | 6 | 5 | 

 

| 4 | 3 | 2 | 1 |

| 5 | 6 | 6 | 5 | 

| 12 | 12 | 12 | 10 | 

| 20 | 19 | 18 | 17 | 

 

마지막 열의 최댓값이 얻을 수 있는 점수의 최댓값이 된다. 

 

이 문제는 DP 동적 계산법을 활용하였다.

 

DP

• 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것
• 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.
• 대표적인 사용 예시로는 피보나치 수열이 있다.

 

https://strong-2-min.tistory.com/190

[프로그래머스] 가장 큰 정사각형 찾기 - DP

 

 

---

다른 사람 풀이

#include <iostream>
#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());
}