코딩테스트 연습 > 땅따먹기 - JAVA

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/12913

프로그래머스

 

풀이 - 나의 생각

dp로 풀어보려고 했는데

 

그냥 단순히 완탐을 해버렸네요 ㅠㅠ

 

현재 위치의 값을 가지고

 

바로 밑에 줄에 있는 값들과 더해 보면서

 

가장 높은 값만 저장합니다.

 

그렇게 마지막까지 가면

 

마지막 줄에는 그 위치에 도달하는 방법 중

 

가장 높은 값일 경우만 모입니다.

 

그 후에 마지막 줄에서 최댓값 한 번 찾아주면 됩니다.

 

ps.

 

코드 길이를 좀 더 줄이고 싶으면 

 

dp[0] = Arrays.copyOf(land[0],y);

 

이렇게 하시면 됩니다.

 

 

코드

 

import java.util.*;
class Solution {
    int solution(int[][] land) {
        int answer = 0;
        int x = land.length, y = land[0].length;
        int[][] dp = new int[x][y];
        dp[0][0] = land[0][0];
        dp[0][1] = land[0][1];
        dp[0][2] = land[0][2];
        dp[0][3] = land[0][3];
        
        for(int i = 0; i < x-1; i++){
            for(int j = 0 ; j < y; j++){
                for(int k = 0; k < y; k++){
                    if(j != k && land[i+1][k] + dp[i][j] > dp[i+1][k]){
                        dp[i+1][k] = land[i+1][k] + dp[i][j];
                    }
                }
            }
        }

        for(int i =0; i < 4; i++){
            answer = Math.max(dp[x-1][i], answer);
        }
        return answer;
    }
}

 

 

 

 

 

 

 

다음에 또 봐요