땅따먹기 lv2

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

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

/*
1. 점수크기순으로 노드정렬 (노드: 점수, 인덱스)
2. 2번째 행부터 시작해서 그전의 행에 최고값인 4번째 열 합산, 만일 동일한 열이라면 3번째 열을 더함.
3. 해당 행 점수 크기순으로 노드 정렬
4. 3반쩨 헹 시작해서 그전의 행인 1번째 행에 최고값인 4번째 열 합산, 만일 동일 열이라면 3번째 열을 더함.

위를 N회 함.
*/
struct node {
    int score;
    int index;
};
vector<vector<node>>lands;
void init(vector<vector<int>> land) {
    for (int y = 0; y < land.size(); ++y) {
        lands.push_back({});
        for (int x = 0; x < land[0].size(); ++x) {
            lands[y].push_back({ land[y][x], x });
        }
    }
}
bool comp(node var, node tar) {
    if (var.score < tar.score)return true;
    return false;
}
int solution(vector<vector<int> > land)
{
    //노드 타입의 벡터에 값(점수, 인덱스)담고
    init(land);
    //정렬
    //0행 정렬
    sort(lands[0].begin(), lands[0].end(), comp);
    for (int y = 1; y < lands.size(); ++y) {
        for (int x = 0; x < lands[0].size(); ++x) {
            if (lands[y][x].index == lands[y-1][3].index) { // 이전의 행의 인덱스와 현 행의 인덱스 같을 때는
                lands[y][x].score += lands[y - 1][2].score; // 2번쨰 인덱스값 즉 4개의 열중 2번째로 높은 값을 더함
            }
            else {
                lands[y][x].score += lands[y - 1][3].score;
            }
        }
        sort(lands[y].begin(), lands[y].end(), comp);
    }
    int idx = land.size() - 1;
    int answer = lands[idx][3].score;


    return answer;
}
int main(void) {
    cout << solution({ {6,7,1,2},{2,3,10,8},{1,3,9,4},{7,11,4,9 } }); // 기댓값 35
}

풀이 설명 ( 못풀었다면 못푼이유 )

-처음에 DFS로 풀었는데 시간초과가 났으며 행 갯수가 100,000으로 너무 깊이가 깊었기에 시간초과가 났을 것이다.

이에 타인 블로그에서 DP로 풀었다는 것에 힌트를 얻어 풀이했다.

DP 문제로 1번째 행을 시작으로 이전의 행의 최고값을 현재 행의 원소에 각각 더한다. 그리고 SCORE기준으로 높은순으로 정렬 하여 다음 행에도 이전 행의 제일큰 값을더한다. 만일 해당 큰 SCORE값인 노드의 인덱스가 현재 행의 원소 노드 인덱스 와 동일 시 그 다음으로 높은 SCORE를 더한다.

 

 

타인 풀이

 

https://velog.io/@younge/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%95%85%EB%94%B0%EB%A8%B9%EA%B8%B0-%EC%97%B0%EC%8A%B5%EB%AC%B8%EC%A0%9CLevel2

[Python] 프로그래머스 - 땅따먹기 (연습문제/Level2)