-
[프로그래머스] 땅따먹기ALGORITHM/PROGRAMMERS 2021. 8. 1. 21:14
https://programmers.co.kr/learn/courses/30/lessons/12913
2021-08-01
123456789101112131415class 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열까지 중에 제일 큰 열의 값을 리턴한다.
'ALGORITHM > PROGRAMMERS' 카테고리의 다른 글
[프로그래머스] 가장 큰 정사각형 찾기 (0) 2021.08.02 [프로그래머스] 삼각 달팽이 (0) 2021.08.01 [프로그래머스] 행렬의 곱셈 (0) 2021.07.30 [프로그래머스] 피보나치 수 (0) 2021.07.30 [프로그래머스] 더 맵게 (0) 2021.07.30