알고리즘 스터디 43일차

1. 땅 따먹기

1) 문제

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

2) 문제 분석 및 풀이

1) 설계, 분석

2) 풀이

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

int solution(vector<vector<int> > land)
{
    int size = land.size();
    vector<vector<int>> dp(size, vector<int>(4));
    for (int i=0; i<4; i++)
    {
        dp[0][i] = land[0][i];
    }

    int answer = 0;

    for (int i=1; i<size; i++)
    {
        dp[i][0] += land[i][0] + max({dp[i-1][1], dp[i-1][2], dp[i-1][3]});
        dp[i][1] += land[i][1] + max({dp[i-1][0], dp[i-1][2], dp[i-1][3]});
        dp[i][2] += land[i][2] + max({dp[i-1][0], dp[i-1][1], dp[i-1][3]});
        dp[i][3] += land[i][3] + max({dp[i-1][0], dp[i-1][1], dp[i-1][2]});
    }

    answer = *max_element(dp.back().begin(), dp.back().end());

    return answer;
}

2. 도둑질

1) 문제

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.
각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

제한 사항
이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

입출력 예
money return
[1, 2, 3, 1] 4

2) 문제 분석 및 풀이

1) 설계, 분석

2) 풀이

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> money) 
{
    int answer = 0;

    int len = money.size();
    vector<int> dpNotVisited1(len);
    vector<int> dpVisited1(len);

    //처음 집을 방문한 경우
    //그 다음집은 방문 못하니 최댓값은 처음 집의 값.
    dpVisited1[0] = money[0];
    dpVisited1[1] = money[0];

    for (int i=2; i<len-1; i++)
    {
        dpVisited1[i] = max( dpVisited1[i-1], dpVisited1[i-2] + money[i]);
    }

    //처음 집을 방문하지 않은 경우
    dpNotVisited1[1] = money[1];
    for (int i=2; i<len; i++)
    {
        dpNotVisited1[i] = max( dpNotVisited1[i-1], dpNotVisited1[i-2] + money[i]);
    }

    answer = max(dpVisited1[len-2], dpNotVisited1[len-1]);

    return answer;
}