728x90
programmers.co.kr/learn/courses/30/lessons/12913
코딩테스트 연습 - 땅따먹기
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟
programmers.co.kr
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> land)
{
int answer=0;
int row = land.size();
for(int i=1; i<row; i++){
land[i][0] += max(land[i-1][1] ,max(land[i-1][2],land[i-1][3]));
land[i][1] += max(land[i-1][0] ,max(land[i-1][2],land[i-1][3]));
land[i][2] +=max(land[i-1][1] ,max(land[i-1][0],land[i-1][3]));
land[i][3] += max(land[i-1][1] ,max(land[i-1][2],land[i-1][0]));
}
answer = max(max(land[row-1][0],land[row-1][1]),max(land[row-1][2],land[row-1][3]));
return answer;
}어떤 알고리즘? 무슨 논리로 해당 알고리즘을 사용?
- 이전단계의 값을 이용하여 현재 단계의 정답을 찾아가는 Dynamic Programming이다. 일단 row의 개수가 4개로 정해져 있어 dp 일것같다는 느낌이 들었다. land[i][0]이라하면이전단계인 i-1 에서 1,2,3 번째 열로 부터 왔을것이다. 매 단계의 규칙이 동일하게 정해져 bottom up 방식으로 풀수 있었다.