[C++] Programmers | 땅따먹기

땅따먹기

프로그래머스

---

---

❌ 실패 #1

// programmers week2-3
// 땅따먹기

#include <bits/stdc++.h>

using namespace std;

int res = 0;

void DFS(vector<vector<int>> land, int cnt, int sum, int prevRow) {
    if (land.size() == cnt) {
        res = max(res, sum);
        return;
    }

    for (int i = 0; i < land[cnt].size(); i++) {
        if (i == prevRow) continue;
        DFS(land, cnt + 1, sum + land[cnt][i], i);
    }
}

int solution(vector<vector<int>> land) {
    DFS(land, 0, 0, -1);
    return res;
}

int main() {
    cout << solution({{1,2,3,5},{5,6,7,8},{4,3,2,1}});
}

 

❌ 실패 #2

// programmers week2-3
// 땅따먹기

#include <bits/stdc++.h>

using namespace std;

int maxVal(vector<vector<int>> land, int col, int row) {
    int val = 0;
    for (int i = 0; i < 4; i++) {
        if (i == row) continue;
        val = max(val, land[col - 1][i]);
    }
    return val;
}

int solution(vector<vector<int>> land) {

    for (int i = 1; i < land.size(); i++) {
        for (int j = 0; j < 4; j++) {
            land[i][j] += maxVal(land, i, j);
        }
    }

    int res = 0;
    for (int i = 0; i < 4; i++) {
        res = max(res, land[land.size() - 1][i]);
    }

    return res;
}

 

✅ Accept Code

 

// programmers week2-3
// 땅따먹기
// Dynamic Programming

#include <bits/stdc++.h>

using namespace std;

int solution(vector<vector<int>> land) {

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

    int res = 0;
    for (int i = 0; i < 4; i++) {
        res = max(res, land[land.size() - 1][i]);
    }

    return res;
}