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

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

코딩테스트 연습 - 땅따먹기

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

int solution(vector<vector<int> > land) {
	for (int i = 1; i < land.size(); i++) {
		land[i][0] = land[i][0] + max(max(land[i - 1][1], land[i - 1][2]), land[i - 1][3]);
		land[i][1] = land[i][1] + max(max(land[i - 1][0], land[i - 1][2]), land[i - 1][3]);
		land[i][2] = land[i][2] + max(max(land[i - 1][0], land[i - 1][1]), land[i - 1][3]);
		land[i][3] = land[i][3] + max(max(land[i - 1][0], land[i - 1][1]), land[i - 1][2]);
	}
	return max(max(max(land[land.size() - 1][0], land[land.size() - 1][1]), land[land.size() - 1][2]), land[land.size() - 1][3]);
}

동적계획법으로 풀었다. 메모리는 따로 사용하지 않았고 주어진 이차원 벡터에 그대로 덮어썼다.

(i행 0열)에 왔다는 것은 i - 1행에서는 0열이 아닌 1열 또는 2열 또는 3열을 거쳤다는 것이기 때문에 (i행 0열)의 값에 (i - 1행 1열), (i - 1행 2열), (i - 1행 3열) 중 최댓값을 더해주었다. 그러면 land[i][0]에는 i행 0열까지 오는 경로 중 가장 최댓값을 가질 수 있는 경로로 왔을 때의 점수가 저장되어있는 것이다. 그런식으로 누적해서 더해서 land[마지막 행]에는 각 열의 최댓값 4개가 저장되어 있다. (4열이기 때문) 그 4개의 숫자 중에서 최댓값이 정답이 된다.