[C++/알고리즘] 프로그래머스 (땅따먹기)

 

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

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

 

처음에는 단순히 뇌빼기를 하고 풀어도 되는 쉬운 문제인 줄 알고 이전값만 더했는데 테스트에서 실패가 뜨는 것을 보고 직감했다. 이게 아니구나.

그래서 다른 방식으로 풀었다. 

원래는 각 행에 가장 큰 값을 더하되 이전 행에서 더했던 인덱스(열)면 다른 최댓값을 찾았었다.

그런데 생각해보니 반례가 있었다.

1	2	3	4
5	6	8	7
9	10	11	12
1	1	3	1000

 

이렇게 극한으로 치닫는 예제에서 4->8->12를 하고나면 마지막행에서 1000을 더할 수가 없게 된다.

그래서 각 행에 이전 행의 최댓값을 더한 후에 비교해줬다. 

 

 

int find_max(int n1, int n2, int n3)
{
	int temp = n1;

	if (temp < n2)
	{
		temp = n2;
	}
	if (temp < n3)
	{
		temp = n3;
	}
	return temp;
}


int solution(vector<vector<int> > land)
{
	int answer = 0;
	int m_size = land.size();

	for (int i = 0; i < m_size-1; ++i)
	{
		land[i+1][0]+= find_max(land[i][1], land[i][2], land[i][3]);
		land[i+1][1]+= find_max(land[i][0], land[i][2], land[i][3]);
		land[i+1][2]+= find_max(land[i][0], land[i][1], land[i][3]);
		land[i+1][3]+= find_max(land[i][1], land[i][2], land[i][0]);
	}

	answer = land[m_size - 1][0];
	for (int i = 1; i < 4; ++i)
	{
		if (answer < land[m_size - 1][i])
		{
			answer = land[m_size - 1][i];
		}
	}
	return answer;
}