[Programmers] 땅따먹기

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12913

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

쉬운 DP 문제였습니다.

cache[y][x] = land[y][x]의 지점부터 얻을 수 있는 최대 점수라는 점만 기억하면 쉽게 접근할 수 있습니다.

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <cstring>
	#include <iostream>
	using namespace std;
	const int COL_MAX = 1e5;
	const int ROW_MAX = 4;
	int cache[COL_MAX][ROW_MAX];
	int getMaxScore(int y, int x, vector<vector<int>> &land)
	{
	if (y == land.size())
	{
	return 0;
	}
	int &result = cache[y][x];
	if (result != -1)
	{
	return result;
	}
	result = land[y][x];
	int temp = 0;
	for (int nextX = 0; nextX < ROW_MAX; nextX++)
	{
	if (nextX == x)
	{
	continue;
	}
	temp = max(temp, getMaxScore(y + 1, nextX, land));
	}
	result += temp;
	return result;
	}
	int solution(vector<vector<int> > land)
	{
	memset(cache, -1, sizeof(cache));
	int answer = 0;
	for (int i = 0; i < ROW_MAX; i++)
	{
	answer = max(answer, getMaxScore(0, i, land));
	}
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~