[프로그래머스 C++] 땅따먹기

[프로그래머스 C++] 땅따먹기

 

https://school.programmers.co.kr/learn/courses/30/lessons/12913

프로그래머스

---

 

해결전략

 

Dynamic Programming (DP)

다이나믹 프로그래밍

 

---

 

처음 시도한 코드 (DFS) - 시간초과

 

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

int answer;

void DFS(int y, int x, int sumNum, vector<vector<int>>& land)
{
	if (y == land.size()){
        if (answer < sumNum) answer = sumNum;
        return;
	}

    for (int i = 0; i < 4; i++)
    {
        if (x == i) continue; // 이전 행의 열과 같은 열이면 갈 수 없다.

        DFS(y+1, i, sumNum + land[y][i], land);
    }
}

int solution(vector<vector<int> > land)
{
    DFS(0, -1, 0, land);

    return answer;
}

 

 

---

 

 

정답 코드

 

#include <vector>
using namespace std;

vector<vector<int>> dp;

int solution(vector<vector<int> > land)
{
    int answer = 0;
    dp.resize(land.size(), vector<int>(4));

    for(int x=0; x<4; x++){
        dp[0][x] = land[0][x];
    }

    int tmpMax = 0;
    for(int y=1; y<land.size(); y++){
	    for(int x=0; x<4; x++)
	    {
            for(int k=0; k<4; k++)
            {
                if (x == k) continue; // 이전 행의 같은 열에서 오는 경우는 빼줘야 한다.

                // 이전 행의 dp[y-1][k]값과 현재 위치를 더해 구한 값을 구한다. 그 중 가장 큰 값을 최종적으로 현재 위치 dp[y][x]으로 설정한다.
                dp[y][x] = max(dp[y][x], dp[y - 1][k] + land[y][x]);
            }

            // 마지막 행의 dp[][]값들 중에서 최대값을 answer에 담기
            if (y == land.size() - 1) {
                if (answer < dp[y][x])
                    answer = dp[y][x];
            }
	    }        
    }
        
    return answer;
}

 

 

---

 

어느 고수의 코드

 

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

 

아.. 나도 이렇게 풀걸..