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

문제는 이 주소로 가면 있습니다.

 

처음에 저는 아래와 같은 코드로 문제를 푸려고 하였습니다.

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> gLand;
int gMax;

void getTotal(int cur, int last, int n, int total) {
  if (cur == n) {
    if (gMax < total) gMax = total;
    return;
  }
  for (int i = 0; i < 4; i++) {
    if (last != i) {
      getTotal(cur+1, i, n, total + gLand[cur][last]);
    }
  }
}

int solution(vector<vector<int>> land) {
  gLand = land;
  for (int i = 0; i < 4; i++) {
    getTotal(0, i, land.size(),0);
  }
  return gMax;
}

 

하지만 "시간초과" 오류가 발생하였습니다. 모든 경우의 수를 다 계산하니 너무 오래 걸리는 것입니다.

 

따라서, 완전탐색으로 접근하기보다 다른 방법을 생각해야 했습니다.

그래서 생각한 것이 "탐욕 (Greedy)" 알고리즘 입니다.

 

↓		(0)	(1)	(2)	(3)	MAX
	(0)	1	2	3	4	max(0) = land[0][3]
	(1)	8	7	6	5	자기까지 오는데 가장 큰 값 = 가능한 위에 값 3개 (1개는 자신과 열이 같으므로 배제) 중 가장 큰 값 + 자신의 값
	(...)	9	10	11	12
	(n-2)	16	15	14	13
	(n-1)	17	18	19	20	max(n-1) = (n-2) 중 가능한 가장 큰 값 + 자기값

힌트는 (n-1) 까지 가는데 가질 수 있는 최고의 값은 (n-2) 까지 가는데 가질 수 있는 최고의 값을 이용해 구할 수 있다는 것입니다. 

 

작성한 코드는 아래에 있습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> land) {
  int row_num = land.size();
  int col_num = 4;

  vector<int> old_max(col_num, 0);
  for (int i = 0; i < col_num; i++) {
    old_max[i] = land[0][i];
  }
  for (int i = 1; i < row_num; i++) {
    vector<int> new_max(col_num, 0);
    for (int j = 0; j < col_num; j++) {
      int total_max = 0;
      for (int k = 0; k < col_num; k++) {
        if ((k != j) && (total_max < old_max[k])) total_max = old_max[k];
      }
      new_max[j] = total_max + land[i][j];
    }
    old_max = new_max;
  }
  return *std::max_element(old_max.begin(), old_max.end());
}