티스토리 뷰

 

#include <algorithm>
#include <vector>

using namespace std;

int solution(vector<vector<int> > land)
{
    int answer = 0;
    int pre_index = -1;
    int now_index = 0;
    int now_max = 0;
    
    for(int i = 0; i < land.size(); i++){
        while(true){
            now_max = *max_element(land[i].begin(), land[i].end());
            now_index = find(land[i].begin(), land[i].end(), now_max) - land[i].begin();
            if (now_index == pre_index){
                land[i][now_index] = 0;
            }
            else break;
        }
        answer += now_max;
        pre_index = now_index;
    }
    return answer;
}

처음에는 그냥 각 행에서 최대값을 더해서 answer 구하면 된다고 생각했는데 위에 처럼 더했다.

그런데 아래와 같은 배열이 주어지면 7 얻어보려다 100을 놓칠 수 있다.

모든 경우의 수를 다 구해서 for문을 엄청 돌려야 하나...

1

3

5

7

3

10

7

100

 

 

해결 방법

하지만, 누적 배열을 사용해야한다는 것을 알았다. 역시 난 하수다.

배열 land[1][2] 에는 land[0][0], land[0][1], land[0][3]  중에서 최대값과 land[1][2] 값을 더한다.

 

1 2 3 5 -> 1 2 3 5
5 6 7 8 -> 10 11 12 11
4 3 2 1 -> 16 15 13 13

 

이런 식으로 이전의 행에서 연속되는 열을 제외하고 최대값을 구해서 현재의 행 값에 더한다. 

그러면 for문을 오조 오억개까지는 아니고 3개 정도로 할 수 있다.

for문을 여기서 더 줄여보고 싶은데 함수를 새로 만들어야하는건가

#include <algorithm>
#include <vector>

using namespace std;

int solution(vector<vector<int> > land)
{
    int answer = 0;
    int i, j, k, maxx = 0;
    for (i = 1; i < land.size(); i++){
        // land[i] 누적 값을 채우기 위해 land[i-1] 배열 탐색
        for(j = 0; j <4; j++){
            // land[i][j] 값을 찾기 위해 land[i-1] 에서 j 빼고 최대값 탐색
            maxx = 0;
            for( k = 0; k <4; k++){
                if(j == k) continue;
                maxx = (maxx > land[i-1][k] ? maxx : land[i-1][k]);
            }
            land[i][j] += maxx;
        }
    }
    answer = *max_element(land[i-1].begin(), land[i-1].end());
    return answer;
}

 

 

 

댓글