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

---

🔗 문제 링크

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

프로그래머스

---

728x90

👩‍💻 코드

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

using namespace std;

int solution(vector<vector<int> > land){
    int n = land.size();
    
    for (int i = 1; i < n; 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]});
    }

    return *max_element(land[n-1].begin(), land[n-1].end());
}

---

📝 풀이

각 열에 대해, 이전 행의 다른 열들 중 최댓값을 더해줍니다.

마지막 행의 최댓값을 return 합니다.

 

⭐ 예시 ⭐

1	2	3	5
5	6	7	8
4	3	2	1

 

for문 i = 1 실행

1	2	3	5
5 + 5 = 10	6 + 5 = 11	7 + 5 = 12	8 + 3 = 11
4	3	2	1

 

for문 i = 2 실행

1	2	3	5
10	11	12	11
4 + 12 = 16	3 + 12 = 15	2 + 11 = 13	1 + 12 = 13