Sandor의 개발 일지

Make real your dreams

1 분 소요

Question

Q

Solution

처음에 완전 탐색으로 모든 수에 대한 결과 값을 vector에 담아 가장 큰 수를 도출 하는 방식으로 풀었다.
시간초과로 인해 풀지 못하여 해설 강의를 참고하여 다시 풀어냈다.

  • (i, 0)을 기준으로 볼때 (i, 1) or (i, 2) or (i, 3) 중에 갈 수 있다.
    같은 열을 제외한 세 가지 중에 최댓값을 확인하여 더해나가면 된다.
  • 총 4열이 있기 때문에 (i, 0), (i, 1), (i, 2), (i, 3) 각각에 대하여 모두 같은 연산을 해준다.
  • 마지막 행에 도달하였을때 vector에 각 4개 열의 최종 결과 값을 넣고 최댓값을 찾으면 된다.

Cord

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

using namespace std;

// 참고 풀이
int solution(vector<vector<int>> land)
{
    int answer = 0;
    vector<int> res;
    int size = land.size();

    //  각각의 열에서 다음 행의 자기 열을 제외한 값 중 가장 큰 값을 찾아 더하며 갱신
    for (int i = 1; i < 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]));

        // 마지막 행에 도달한 4개의 열에 대한 값을 vector에 저장
        if (i == size - 1)
        {
            res.push_back(land[i][0]);
            res.push_back(land[i][1]);
            res.push_back(land[i][2]);
            res.push_back(land[i][3]);
        }
    }

    return answer = *max_element(res.begin(), res.end());
}

// -------------------------------- 시간 초과 테스트 실패 ------------------------------------------------
vector<int> res;
int prohibitColumn = -1;    // 금지 열

void sumValue(vector<vector<int>>& land, int row, int prohibitColumn, int sum)
{
    if (row >= land.size()) { res.push_back(sum); return; }

    for (int column = 0; column < 4; ++column)
    {
        if (prohibitColumn != column)
        {
            sumValue(land, row + 1, column, sum + land[row][column]);
        }
    }
}

// 완전탐색 재귀 활용
int solutionFail(vector<vector<int>> land)
{
    int answer = 0;
    sumValue(land, 0, prohibitColumn, answer);
    return answer = *max_element(res.begin(), res.end());
}

// --------------------------------------------------------------------------------------------------------

Result

Result

참고