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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

동적계획법 문제이다. dp[i][j]는 i-1번째 열에 저장된 값 중 dp[i-1][j]를 제외한 값 중에서 최대값에 land[i][j]를 더한 값이 되어야한다.

코드

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<vector<int>> land)
{
    int answer = 0;
    vector<vector<int>> dp(land.size(), vector<int>(land[0].size(), 0));
    for (int i = 0; i < land[0].size(); i++) dp[0][i] = land[0][i];
    for (int i = 1; i < land.size(); i++) {
        for (int j = 0; j < land[0].size(); j++) {
            for (int l = 0; l < land[0].size(); l++) {
                if (j == l) continue;
                dp[i][j] = max(dp[i][j], dp[i-1][l] + land[i][j]);
            }
        }
    }

    for (int i : dp[dp.size() - 1])
        answer = max(answer, i);
    return answer;
}

Java

class Solution {
    int solution(int[][] land) {
        int answer = 0;
        int[][] dp = new int[land.length][land[0].length];
        for(int i=0; i<land[0].length; i++) dp[0][i] = land[0][i];
        for(int i=1; i<land.length; i++){
            for(int j=0; j<land[i].length; j++){
                for(int l=0; l<land[i-1].length; l++){
                    if(j == l) continue;
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][l] + land[i][j]);
                }
            }
        }
        for(int i : dp[dp.length-1])
            answer = Math.max(answer, i);
        return answer;
    }
}