Algorithm/Programmers
[Algorithm] Programmers :: 땅따먹기
MaxLevel
2023. 5. 21. 02:32
https://school.programmers.co.kr/learn/courses/30/lessons/12913
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
int dp[100001][4] = { 0 };
int solution(vector<vector<int> > land)
{
int answer = 0;
int rowSize = land.size();
for (int i = 0; i < 4; ++i)
{
dp[0][i] = land[0][i];
}
for (int i = 1; i < rowSize; ++i)
{
dp[i][0] = land[i][0] + max({ dp[i - 1][1], dp[i - 1][2], dp[i - 1][3] });
dp[i][1] = land[i][1] + max({ dp[i - 1][0], dp[i - 1][2], dp[i - 1][3] });
dp[i][2] = land[i][2] + max({ dp[i - 1][0], dp[i - 1][1], dp[i - 1][3] });
dp[i][3] = land[i][3] + max({ dp[i - 1][0], dp[i - 1][1], dp[i - 1][2] });
}
answer = max({ dp[rowSize - 1][0],dp[rowSize - 1][1], dp[rowSize - 1][2], dp[rowSize - 1][3] });
return answer;
}
|
cs |
DP문제의 연습문제로 추천할만한 문제이다.
다음 행에선 같은열로는 이동을 못 한다 했으니, 아래로 쭉 업데이트해주면서 해당 칸의 값(land[i][0]) + 그 전 행의 같은열을 제외한값들 중 최대값 으로 dp테이블을 업데이트하면 된다.
현재 그냥 c++, 2레벨짜리 풀어보고있는데 유난히 DP문제가 많은듯하다;