ALGORITHM/PROGRAMMERS
[프로그래머스] 땅따먹기
0298
2021. 8. 1. 21:14
https://programmers.co.kr/learn/courses/30/lessons/12913
코딩테스트 연습 - 땅따먹기
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟
programmers.co.kr
2021-08-01
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
int solution(int[][] land) {
int[][] dp = new int[land.length][land[0].length];
System.arraycopy(land[0], 0, dp[0], 0, land[0].length);
for(int i = 1; i < land.length; i++) {
dp[i][0] = land[i][0] + Math.max(dp[i-1][3], Math.max(dp[i-1][1], dp[i-1][2]));
dp[i][1] = land[i][1] + Math.max(dp[i-1][0], Math.max(dp[i-1][2], dp[i-1][3]));
dp[i][2] = land[i][2] + Math.max(dp[i-1][0], Math.max(dp[i-1][1], dp[i-1][3]));
dp[i][3] = land[i][3] + Math.max(dp[i-1][0], Math.max(dp[i-1][1], dp[i-1][2]));
}
return Math.max(Math.max(dp[land.length-1][0], dp[land.length-1][1]), Math.max(dp[land.length-1][2], dp[land.length-1][3]));
}
}
|
cs |
#문제풀이
4열밖에 없어서 dp로 풀었다.
1. 일단 0행을 다 복사해서 dp배열에 넣는다.
2. 1행 부터 돌아가면서 경우의 수를 나눠서 체크를 한다.
1) dp[i][0] : 0열을 선택했을 경우 + 그 전 행의 1, 2, 3열 중에 제일 큰 값
2) dp[i][1] : 1열을 선택했을 경우 + 그 전 행의 0, 2, 3열 중에 제일 큰 값
3) dp[i][2] : 2열을 선택했을 경우 + 그 전 행의 0, 1, 3열 중에 제일 큰 값
4) dp[i][3] : 3열을 선택했을 경우 + 그 전 행의 0, 1, 2열 중에 제일 큰 값
3. 마지막 행의 0열부터 3열까지 중에 제일 큰 열의 값을 리턴한다.
