[C++] level2 땅따먹기 12913

참고자료 https://hwan-shell.tistory.com/202
해당 문제는 위 블로그를 참고하여 해결하였습니다.

📌땅따먹기

/* 해당 문제 설명은 링크로 대체한다. */

📌풀이

처음에 규칙을 지키면서 최고점을 구하는 완전 탐색 방식으로 풀이했더니 시간초과가 발생했다.
이런 최고점을 구하는 문제의 경우 DP를 이용하는게 적합하다는 구글링을 보았고, DP는 공부하지 않았기 때문에 공부하고 코드를 다시 보니 이해할 수 있었다.

DP?
: 문제를 작은 인스턴스들로 나누고 상향식(Bottom-up) 순서로 풀어나가면서 문제의 값을 정해놓고 필요할 때 가져와 문제를 해결하는 방식이다.
//기억하며 풀기(Memoization)라 생각하면 된다.
//점화식을 세울 수 있어야 함

이 문제에서의 점화식은 각 행별로 큰 값을 찾아서 더해 최고점을 구하는 것!
해당 문제에서는 (n x 4) 배열로 정의되어 있으므로 점화식을 세우면 다음과 같다.

//max 함수는 인자가 2개만 들어감
//max로 한 번 더 싸거나 max를 별도로 구하는 방법을 모색해야 함
land[i][0] + max(land[i-1][1], land[i-1][2], land[i-1][3])
land[i][1] + max(land[i-1][0], land[i-1][2], land[i-1][3])
land[i][2] + max(land[i-1][0], land[i-1][1], land[i-1][3])
land[i][3] + max(land[i-1][0], land[i-1][1], land[i-1][2])

📌코드

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

//이전 행에서 가장 큰 값 찾음
int getMax(vector<int> v, int idx)
{
    int temp = 0;
    for (int i = 0; i < 4; i++)
    {
        if (i != idx)
            temp = max(temp, v[i]);
    }
    return temp;
}

int solution(vector<vector<int>> land)
{
    int answer = 0; //최고점

    // (n x 4) 배열
    for (int i = 1; i < land.size(); i++)
    {
        for (int j = 0; j < 4; j++)
        {
            land[i][j] += getMax(land[i - 1], j); //이전 행에서 가장 큰 값을 현재 행에 더해줌
            answer = max(answer, land[i][j]);     //계속 갱신
        }
    }

    return answer;
}

DP 방식과 max_element()
처음엔 DP 방식을 이용하지 않으면 max_element()함수를 이용하여 해결할 수 없음!
DP를 이용하면 충분히 해결 할 수 있음!!!!!!
처음에 시도했으나 DP 몰랐을 때 시도해보았으나 각 행별로 큰 값을 저장할 수 없는 문제가 발생하여 이 좋은 함수를 못쓴다고라고라?고라? 하면서 좌절했으나 .... 다른 사람들의 풀이를 보니 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());
}

---

회고

충분히 풀어낼 수 있는 문제였지만, DP를 몰랐다... ㅎ....
그래도 이번 기회를 통해 DP를 알게되었으니 다행이다.
분할정복을 알고 있던터라 다행히 이해하는데 많이 어렵진 않았다.