(프로그래머)(C++)(12913)

(질문의 출처)

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

1. 문제

설명하다

랜드 그랩 게임을 하려고 합니다.

랜드 그랩 게임의 랜드는 N개의 행과 4개의 열로 구성되며 점수는 모든 그리드에 기록됩니다.

첫 번째 줄부터 땅을 밟기 시작하고, 한 줄씩 내려갈 때는 각 줄의 네 칸 중 한 칸만 밟아야 내려옵니다.

그러나 특별한 규칙이 있습니다.

즉, 한 번에 한 행씩 드롭하고 같은 열을 계속 밟을 수 없습니다.

예를 들어,

|1|2|3|5|

5|6|7|8|

|4|3|2|1|

토지가 로 주어지면 1열의 4번째 칸(5)을 밟으면 2열의 4번째 칸(8)을 밟을 수 없습니다.

모든 행이 마지막 행으로 내려갔을 때 얻을 수 있는 최대 점수를 반환하여 솔버 함수를 완성하십시오. 위의 예에서 1행 4열(5), 2행 3열(7), 3행 1열(4)을 밟으면 16점이 최고 점수가 되므로 16을 반환한다.

한계

• 행 개수 N: 100,000 이하의 자연수
• 열의 수는 4개이고 land는 2차원 배열로 주어진다.
  
  
• 점수: 100보다 작거나 같은 자연수

입력 및 출력 예

2. 설명

일반적인 dfs 문제인 줄 알고 다 풀었는데 테스트 케이스는 통과했는데 제출을 해보니 다들 당황스럽게 타임아웃이 되더군요. 그래서 어떻게 하면 좋을까 고민하다가 dp를 사용하는 방법이 있습니다.

이전 행의 최대값을 다음 행에 추가하여 이를 수행합니다.

코드는 간단하지만 비슷한 유형이 있으면 또 다른 헤멜 문제인 것 같습니다.

dp 문제를 많이 풀어야 할 것 같은 느낌이 듭니다.

3. 코드

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


using namespace std;

int solution(vector<vector<int> > land)
{
    int answer = 0;
    
    for(int i=1; i<land.size(); i++){
        land(i)(0) += max({land(i-1)(1), land(i-1)(2), land(i-1)(3)});
        land(i)(1) += max({land(i-1)(0), land(i-1)(2), land(i-1)(3)});
        land(i)(2) += max({land(i-1)(0), land(i-1)(1), land(i-1)(3)});
        land(i)(3) += max({land(i-1)(0), land(i-1)(1), land(i-1)(2)});
        
        //cout<<land(i)(0)<<" "<<land(i)(1)<<" "<<land(i)(2)<<" "<<land(i)(3)<<"\n";
    }
    
    answer=max({land(land.size()-1)(0), land(land.size()-1)(1), land(land.size()-1)(2), land(land.size()-1)(3)});
    
    return answer;
}