도둑질 42897

문제

접근 방법

여러 경우를 작성해보자.

1	2	3	1
1	2	4	3

입출력 예로 나타난 것이다. 건너뛰며 확인해주면 되는 것을 알게 됐다.

5	1	5
5	1	5

10이 나올 것 같지만 5가 나오는 것이 맞다. 동그랗게 배치됐기 때문이다.

5	1	1	5	1
5	1	6	10	1

6이 나올 것 같지만 2칸을 건너서 10이라는 값을 가질 수 있다.

5	1	5	1	15
5	1	10	6	20

무작정 더하고 첫 번째, 마지막 중 작은 값을 빼서 인접한 부분을 해소하기에는 첫 번째 거가 최종 답엔 사용 안 됐을 수도 있다. 전체 크기가 홀수인지 짝수인지를 통해 해결하기에도 1칸을 뛰어넘는 것이 아닌 2칸을 뛰어넘는 경우의 존재로 인해 무산된다. (2칸을 뛰어넘으면 홀수와 짝수가 혼합된다)

5	1	5	1	5	5	1	5	1	15
5	0	10	6	15	15	16	20	17
	1	5	2	10	10	11	15	12	30
		5	1	10	10	11	15	12	30

심플하게 생각하기로 했다.
1번째 시작일 경우, 2번째 시작일 경우, 3번째 시작일 경우를 두어서 확인하는 것이다. 그렇게 된다면 두, 세 번째는 첫 번째를 사용 안 했기에 마지막 경우를 사용할 수 있고 첫 번째는 마지막 거를 사용 안 하면 되는 것이다.

코드

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> money)
{
    vector<vector<int>> dp(3, vector<int>(money.size()));
    dp[0][0] = money[0];
    dp[1][1] = money[1];
    dp[2][2] = money[2];
    if (money.size() != 3)
    {
        dp[0][2] = dp[0][0] + money[2];
    }
    for (int i = 3; i < money.size(); ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            dp[j][i] = money[i] + max(dp[j][i - 2], dp[j][i - 3]);
        }
    }
    return max(max(max(dp[0][money.size() - 2], dp[0][money.size() - 3]), max(dp[1][money.size() - 1], dp[1][money.size() - 2])), max(dp[2][money.size() - 1], dp[2][money.size() - 2]));
}

풀이

1번째 시작, 2번째 시작, 3번째 시작을 채워두고 시작하면 된다. 2, 3번째는 1번째 시작이 비어있기에 값을 가져오려 해도 0인 것이다. 1번째 시작은 1번째 시작했기에 마지막 값을 사용 안 하는 것이다.
문제가 잘 안 풀리면 간단하게 접근하는 게 맞는 것 같다.

22.12.28 해결하고 난 뒤 다른 사람들 풀이를 찾아보니 첫 번째를 사용하고 마지막을 사용 안 하는 경우, 첫 번째를 사용 안 하고 마지막을 사용하는 경우로 나누어서 해결했다. 위에 작성한 표를 봐도 알겠지만 2번째 시작과 3번째 시작은 동일한 결과를 냈다. 불필요한 부분을 미리 확인하고 제거하는 것 또한 중요한 부분인 것 같다.
또한 이전의 값이 더 높으면 그대로 가져와서 배치해두는 것이 더 간결한 코드를 만들어낸다. 졸려서 실수를 많이 한 것 같다.