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

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

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

 

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

 

처음에는 완탐으로 풀었으나 당연히 시간초과 나버림..

모든 경우의 수를 구하는 거니 경우의 수가 4*3^(N-1) 인데, N은 10000이하의 자연수..

 

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

int answer = 0;
void dfs(int r, int c, int sum, vector<vector<int>> land) {
	if (r == land.size() - 1) {
		answer = max(answer, sum);
		return;
	}

	for (int i = 0; i < 4; i++) {
		if (i == c) continue;
		dfs(r + 1, i, sum + land[r + 1][i], land);
	}
}

int solution(vector<vector<int> > land) {
	dfs(-1, -1, 0, land);
	return answer;
}

 

 

DP로 바꿔서 풀었다.

 

land[i][j]를 선택했을 때까지의 최댓값

dp[i][j] = dp[i-1] 행의 값들 중 최댓값 + land[i][j]

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

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

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

	for (int i = 1; i < N; i++) {
		for (int j = 0; j < 4; j++) {
			int mx = 0;
			for (int k = 0; k < 4; k++) {
				if (k == j) continue;
				mx = max(mx, dp[i - 1][k]);
			}
			dp[i][j] = mx + land[i][j];
		}
	}

	for (int i = 0; i < 4; i++) {
		answer = max(answer, dp[N - 1][i]);
	}

	return answer;
}

 

다른 사람이 푼 코드

열이 4개로 고정되어있으니 이렇게 푸는게 점화식도 잘 보이고 가독성이 높은 것 같다..

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