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

programmers.co.kr/learn/courses/30/lessons/12913

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

처음 문제를 접했을때 DP로 푸는 것임을 직감할 수 있었다.

 

좀 더 깔끔하게 문제를 풀고 싶었는데 좋은 방법이 생각이 안나서 그냥 무작정 모든 경우의 수를 나눠서 풀었다.

 

DP배열 크기를 실수로 40004로 하니 segmentaion fault가 났던 것을 생각하면 항상 배열이나 벡터를 선언할때

사이즈를 잘보고 넉넉하게 선언하는 것이 중요할 것 같다.

 

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

int cmp(int a, int b, int c){
    int temp;
    temp = max(a,b);
    temp = max(temp, c);
    return temp;
}

int dp[400000];

int solution(vector<vector<int>> land){
    int answer = 0;
    int a = 0;
    for(int i = 0; i < land.size(); i++){
        for(int j = 0; j < 4; j++){
            dp[a] = land[i][j];
            a++;
        }
    }
    int n = land.size()*4;
    for(int i = 4; i < n; i++){
        if(i % 4 == 0){
            dp[i] += cmp(dp[i-1], dp[i-2], dp[i-3]);
        }else if(i % 4 == 1){
            dp[i] += cmp(dp[i-2], dp[i-3], dp[i-5]);
        }else if(i % 4 == 2){
            dp[i] += cmp(dp[i-3], dp[i-5], dp[i-6]);
        }else{
            dp[i] += cmp(dp[i-5], dp[i-6], dp[i-7]);
        }
    }
    answer = cmp(dp[n-1],dp[n-2],dp[n-3]);
    answer = max(answer, dp[n-4]);
    return answer;
}