[Programmers]#Level2_땅 따먹기, DP

 

#1. 문제

 

프로그래머스

 

---

 

#2. 풀이

 

1. 동적 계획법(Dynamic Programming)

 

[알고리즘]#5_동적 계획법

 

동적 계획법은 최적화 문제를 해결하는 데 사용되는 알고리즘 디자인 기법 중 하나로, 입력 크기에 따라 중복되는 하위 문제들을 재귀적으로 해결하고, 결과 값들을 기억하는 것으로 중복 계산을 방지함으로써 효율적으로 최적해를 찾습니다.

 

2. 이전 행의 같은 위치의 열을 제외한 열에 위치한 값들 중 최고를 찾아라!

 

1. 두 번째 행(0-based indexing)부터 열을 차례대로 순회합니다. 이때, 현재 행의 열들을 순회하며, 각자 이전의 행의 열에 위치한 값들 중 최대 값을 자기 자신의 값에 더해줍니다. 이때, 물론 자신과 동일한 열에 위치한 값은 제외됩니다.
2. 그리고, 마지막 행에 위치한 값들 중 최대 값을 결과값으로 출력해 줍니다. 

 

---

 

#3. 코드

 

/*
    @문제 : 서로 다른 '열'을 밟으며, 각 행을 지나며 쌓인 총 합이 최대가 되는 수
    @설명
            1. BFS 혹은 DFS 활용할 경우, 시간 초과 발생!
            2. DP 활용
*/

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

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

    for (int row = 1; row < land.size(); ++row)
    {
        for (int col = 0; col < land[row].size(); ++col)
        {
            int maxVal = 0;
            for (int k = 0; k < land[row].size(); ++k)
            {
                if (k != col)
                    maxVal = max(maxVal, land[row - 1][k]);
            }
            land[row][col] += maxVal;
        }
    }

    for (int i = 0; i < land[0].size(); ++i)
    {
        answer = max(answer, land[land.size() - 1][i]);
    }

    return answer;
}

 

---