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

안녕하십니까. Eun🦆입니다.

풀이법 입니다.

 

코딩테스트 연습 - 땅따먹기

#include <iostream>
#include <vector>
using namespace std;
// 첫 행부터 다음 행의 최대값을 더해 구하려고 했으나 이는 틀리다.
// 왜냐하면 다음 행의 중간값을 더하고 이 다음 행의 최대값을 더하는 경우 더 클 수 있기 때문이다.
// 해결 방안은 다음 행의 값들에 이전 행의 최대값을 더하는 것이다.(같은 열 제외)
// DFS의 경우 시간복잡도로 인해 불가능하다고 한다.
int solution(vector<vector<int> > land)
{
    int answer = 0;
    for(int y=1;y<land.size();y++)
    {
        for(int x=0;x<land[0].size();x++)
        {
            int MAX = 0;
            for(int k=0;k<land[0].size();k++)
            {
                if(k!=x & MAX < land[y-1][k])
                {
                    MAX = land[y-1][k];
                }
            }
            land[y][x] += MAX;
            //printf("x=%d,y=%d,land[%d][%d]=%d\n",x,y,y,x,land[y][x]);
            if(y==land.size()-1)
            {
                if(answer < land[y][x])
                    answer = land[y][x];
            }
        }
    }
    return answer;
}

 

네이버 블로그 리뉴얼입니다.

(https://blog.naver.com/unsuk1/221952810771)