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

22 Jan 2023 in Study on Coding Test

dp를 이용하여 푸는 문제

참고링크

정답제출코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int solution(vector<vector<int> > land)
{
    int answer = 0;
    
    int land_len = land.size();
    
    for (int i = 1; i < land_len; ++i)
    {
        land[i][0] += max(land[i-1][1], max(land[i-1][2], land[i-1][3]));
        land[i][1] += max(land[i-1][0], max(land[i-1][2], land[i-1][3]));
        land[i][2] += max(land[i-1][0], max(land[i-1][1], land[i-1][3]));
        land[i][3] += max(land[i-1][0], max(land[i-1][1], land[i-1][2]));
    }
    
    answer = max(max(land[land_len-1][0], land[land_len-1][1]), max(land[land_len-1][2], land[land_len-1][3]));

    return answer;
}

삽질 및 구글링 끝에 위의 정답코드를 제출했다..

오답제출 코드

#include <iostream>
#include <vector>

using namespace std;

int land_len, score = 0;
vector<vector<int>> land_static;
vector<int> scores;

int get_sum(vector<int> s)
{
    int _sum = 0;
    int len = s.size();
    
    for (int i = 0; i < len; ++i)
    {
        _sum += s[i];        
        //cout << s[i] << ' ';
    }
    //cout << '\n';
    
    return _sum;
}

void recur(int row, int col)
{
    if (row == land_len)
    {
        int score_can = get_sum(scores);
        
        if (score_can > score)
            score = score_can;
        return;
    }

    for (int i = 0; i < 4; ++i)
    {
        // 같은 열일 경우 생략
        if (i == col)
            continue;
        
        scores.push_back(land_static[row][i]);
        recur(row+1, i);
        scores.pop_back();
    }
}

int solution(vector<vector<int> > land)
{
    int answer = 0;
        
    land_len = land.size();
    land_static = land;
    
    for (int i = 0; i < 4; ++i)
    {
        scores.push_back(land_static[0][i]);
        recur(1, i);
        scores.pop_back();
    }
    
    answer = score;
    return answer;
}

백트래킹이라고 생각해서 모든 경우의 수를 탐색하는 방법을 사용했는데,

모든 테스트케이스에서 시간초과가 떠서 매우 당황했다.

근데 알고보니 웬걸, 구글링해서 찾아보니 DP였네?

아하하;; 너무 어렵게 생각했나보다. 그냥 가장 큰 수를 더하면서 더해나가면 되는 것이었다.

하.. dp는 역시 너무 어렵다..

그리고 구글링을 해보니 다들 algorithm 헤더에 있는 max 함수를 많이 사용하신것 같다.

나도 앞으론 나도 이를 활용해야겠다.