땅따먹기

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

using namespace std;

int solution(vector<vector<int>> land)
{
    int answer = 0;
    
    int before_idx = -1;
    for (int i = 0; i < land.size(); ++i) {
        vector<int> row = land[i];
        
        int max = *max_element(row.begin(), row.end());
        int max_idx = max_element(row.begin(), row.end()) - row.begin();
        if (before_idx == -1 || (before_idx != -1 && max_idx != before_idx)) {
            answer += max;
            before_idx = max_idx;
        } else {
            nth_element(row.begin(), row.begin()+1, row.end(), greater<int>());
            max = row[1];
            answer += max;
            auto it = find(land[i].begin(), land[i].end(), max);
            before_idx = it - land[i].begin();
        }
        // cout << "max: " << max << endl;
    }
    
    return answer;
}

• 시간 초과
• DP 또는 Greedy로 풀이해야 함

DP로 다시 풀이

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

int solution(vector<vector<int>> land)
{
    int answer = 0;
    int totalSize = land.size()-1;
    for(unsigned i = 0; i < totalSize; i++){
        int land0 = land[i][0];
        int land1 = land[i][1];
        int land2 = land[i][2];
        int land3 = land[i][3];
        // i번째 행에서 선택할 수 있는 최댓값을 저장하는 i+1번째 행 할당
        // totalSize-1까지 순회하므로, land[totalSize]는 주어진 모든 행을 순회했을 때의 최댓값
        // 이전에 밟은 열을 연속해서 밟을 수 없으므로,
        // n번째 열에 해당 열을 제외한 다른 열의 값 중 최댓값을 저장
        land[i+1][0] += max(land1, max(land2, land3));
        land[i+1][1] += max(land0, max(land2, land3));
        land[i+1][2] += max(land0, max(land1, land3));
        land[i+1][3] += max(land0, max(land1, land2));
    }

	// 최댓값 중 가장 높은 값 반환
    answer = max(max(land[totalSize][0], land[totalSize][1]), max(land[totalSize][2], land[totalSize][3]));
    return answer;
}

• 참고: https://husk321.tistory.com/277

멀리뛰기

#include <string>
#include <vector>

#define mod 1234567

long long solution(int n) {
	long long dp[2001];
    
    dp[1] = 1;  // 1칸까지 가는 방법(1칸)
    dp[2] = 2;  // 2칸까지 가는 방법(1칸, 1칸), (2칸)
    
    for (int i = 3; i <= n; ++i)
    {
    	dp[i] = dp[i-1] + dp[i-2];
    }
    
    return dp[i] % mod;
}

• N칸까지 가는 방법은 N-1칸에서 1칸 이동 또는 N-2칸에서 2칸 이동
• 따라서 N칸까지 가는 방법의 수는 N-1칸까지 가는 방법의 수 + N-2칸까지 가는 방법의 수