[프로그래머스/Lv. 2] 땅따먹기 (JAVA)

📖 문제

프로그래머스

 

 

💡  풀이 방식

• DP

1. dp 배열의 값을 초기화한다.

   - 0번째 행의 값은 land 배열의 값 그대로 채운다.

 

2. 1 ~ (land.length - 1)행까지 dp 배열을 채운다.

  - 0번째 열인 경우, 이전 행의 1,2,3열의 값 中 큰 값과 land배열에서 현재 좌표 위치에 있는 값 land[i][0]을 더한다.

  - 1번째 열인 경우, 이전 행의 0,2,3열의 값 中 큰 값과 land배열에서 현재 좌표 위치에 있는 값 land[i][1]을 더한다.

  - 2번째 열인 경우, 이전 행의 0,1,3열의 값 中 큰 값과 land배열에서 현재 좌표 위치에 있는 값 land[i][2]을 더한다.

  - 3번째 열인 경우, 이전 행의 0,1,2열의 값 中 큰 값과 land배열에서 현재 좌표 위치에 있는 값 land[i][3]을 더한다.

 

3. 마지막 행에서 최댓값을 구하고 출력한다.

 

 

 

💥 유의사항

완전탐색으로 풀면 틀린다

 

 

🔺 코드

import java.util.*;
 
class Solution {
    int solution(int[][] land) {
        int answer = 0;
        int len = land.length;
        
        int[][] dp = new int[len][4];
 
        // dp 배열 0번째 행 값 초기화
        for(int i = 0 ; i < 4 ; i++) {
            dp[0][i] = land[0][i];
        }
        
        // dp 배열 값 채우기 (이전 행에서 다른 3열의 값 중 가장 큰 값 찾아 현재 land 배열 칸의 값과 더하기)
        for(int i = 1 ; i < len ; i++) {
            dp[i][0] = getMax(dp[i - 1][1], dp[i - 1][2], dp[i - 1][3]) + land[i][0];
            dp[i][1] = getMax(dp[i - 1][0], dp[i - 1][2], dp[i - 1][3]) + land[i][1];
            dp[i][2] = getMax(dp[i - 1][0], dp[i - 1][1], dp[i - 1][3]) + land[i][2];
            dp[i][3] = getMax(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]) + land[i][3];
        }
        
        // 마지막 행에서 가장 큰 값 찾아 출력하기
        for(int i = 0 ; i < 4 ; i++) {
            answer = Math.max(answer, dp[len - 1][i]);
        }
 
        return answer;
    }
    
    // 세 값 중 가장 큰 값 구하는 메소드
    private static int getMax(int a, int b, int c) {
        return Math.max(Math.max(a, b), c);
    }
}

 

 

➕ 다른 풀이 방식

- 더 간단하게는 이렇게,, dp배열 따로 만들 필요가 없었던 것이다,,

[프로그래머스] level2. 땅따먹기 (자바 JAVA)

 

 

- 이런 3중 for문 풀이도..!

[프로그래머스] 땅따먹기 (JAVA)

---

💦 어려웠던 점

처음에 그저 완탐,, 으로 풀 생각을 하였는데 그게 아니라 DP 문제였던 것이다,,

30분 완탐해보다가 안되어서 DP로 풀어봤더니 맞았다,,,

좀 접근 방식 찾기까지 돌아오긴 했지만 그래도 혼자 풀어서 뿌듯해ㅠㅠ

 

 

 

1회독	2회독	3회독	4회독	5회독
V