DP문제는 언제나 어렵다.

해당 해설은 최대한 쉽게 푸려고 썼지만,

DP가 워낙 난이도가 있다보니, 이 글을 보고 이해를 할지는 잘 모르겠다.

가장 단순하게 생각하자면,
도둑질 할 대상은 항상 떨어져있어야한다.
그럼, 초보자는 분명 이렇게 생각 할 것이다. 홀수번 끼리 더한 값하고,
짝수번 끼리 더한 값을 비교해서 가장 큰 값을 선택하면 되겠네?
자신있게 코드를 후다닥 작성하여 채점 돌리면 거의 다 틀려서 전멸에 가까울 것이다.
그럼, 이제서야 레벨4의 위엄을 알게되지 않을까?

위의 경우가 안되는 이유는 아마 쉽게 알아냈을 것이다.
[1000, 10, 10, 2000, 30] = 3000
위와 같은 경우면은, 홀수번 위치의 합과, 짝수번 위치의 합을 더해서,
3000이라는 수를 만드는 것이 불가능하다는 사실은 보면 알 것이다.

그러면, 우리는 다른 방식으로 최댓값을 구할 필요가 있다는 것을 알게되었다.
천천히 배열의 길이를 늘리면서 느긋하게 생각해볼 필요가 있다.

[1, 2]

위와 같이 도둑질 할 집이 2개 있다고 치자, 이득을 취할려면, 당연히 2를 선택해야 할 것이다.(물론 이런 테케는 존재하지 않음.)

하나 더 늘려볼까?

[1, 2, 3]

3개가 있다고 하면은? 당연히 3을 고를 것이다.
설마, 1번과 3번을 고르는 말도 안되는 경우를 생각하진 않길 바란다.

하나 더 늘려보자.

[1, 2, 3, 4]
단순히 생각해봐도, 2와 4를 고르는 경우일 것이다.
길이가 4개인 경우부터는 2개이상 고를 수 있다는 사실을 알게 되었다.

하나 더,

[1, 10, 20, 4, 40]
가장 큰 조합은 20과 40을 선택하는 합 60일 것이다.
여기서 부터 뭔가 머릿속이 복잡해지지 않는가?
순서대로 비교를 하려면 처음부터 선택해서 선택을 하든가 해야하는데,
정답을 보자면, 1과 10은 선택조차 당하지 않았다.
기분이 매우 나이스해진다.
우리는 이런 이상한 규칙을 적중시키는 DP점화식을 세울 필요가 있다.
문제가 존재한다는 건, 어딘가 규칙은 있을테니 말이다.
처음부터 1과 10부터 비교해보자, 둘 중에 고르자면, 나는 10을 고르겠다.
그 다음은, 10을 골랐으면, 4말고는 고를게 없다. 그럼 14가 될 것이다.
그런데 4이전의 숫자를 보니까, 훨씬 더 큰 20이라는 수가 존재한다.
그래서 14를 던져버리고 나는 20을 선택했다. 그리고나서 선택할 수 있는 수를 보니, 40이 있다.
40도 마저 선택하면, 답은 60이 된다.
위와 같은 알고리즘을 통하여 답을 유추할 수 있다.

여기서 우리는 점화식을 도출해낼 수 있는데, 아직까지는 시간이 좀 걸릴 것 같다.

우리는 최대한 큰 수를 고를 수 있는 모든 경우를 알아봐야하므로, 모든 위치에서의 최고의 값을 고를 수 있는 경우를 알아야한다.

사실 위와 같은 방법으로 60을 고르는 것은 너무 일방적인 방법이다.

좀 더 포괄적인 방법을 적용시킬 필요가 있다.

[1, 10, 20, 4, 40]

위의 배열에서 각각의 현재 위치에서 선택할 수 있는 최선의 경우를 누적하면서 연산을 해보겠다.

처음에 1의 위치에서 가장 큰 경우는 자기 자신을 선택하는 경우가 될 것이다.

[1, 10, 20, 4, 40]과 같은 그대로의 결과가 도출된다.

그 다음, 10의 위치에서 봤을 때는, 1을 고르는 방법이 없으므로, 10을 그대로 반환합니다.

[1, 10, 20, 4, 40]과 같은 아직까지도 그대로의 결과가 도출된다.

그 다음 20의 위치에서 봤을 때는, 2번째의 값을 고르면, 자기자신을 선택하지 못한다.
그렇지만, 자기자신을 선택하면, 1번을 고른 경우가 붙어있지 않으므로, 같이 합산하여 누적할 수 있다.
그럼 각각 두 경우를 비교하여, 가장 큰 값을 고르는 경우가 현재 위치에서의 가장 최고의 선택이 될 것이다.
그럼 10과 1+20을 비교하므로 당연히 1+20이 크므로 해당 위치는 21값을 최고값으로 선택할 수 있는 위치가된다.

[1, 10, 21, 4, 40]과 같이 가운데 값이 20에서 1을 더한 21의 값으로 갱신되었다.

여기까지 이해했다면, 진짜 나이스한 것이다. 거의 반을 이해한 것이나, 다름없다.

다음 위치는 4의 기준이다. 4는 한 칸 떨어진 10의 위치에서 고를 수 있는 최고값을 자기자신의 값에 더할 수 있다.
하지만 전의 위치 21을 고른다면, 자기자신을 선택할 수 없게 될 것이다. 그러면 당연히 값이 큰 21을 고르게 될 것이다.

[1, 10, 21, 21, 40]과 같은 배열을 만들 수 있다.

이로써 우리는

현재위치값 = Max(전위치의최고선택값, 전전위치의최고선택값 + 현재위치의값)

와 같은 수식을 도출해낼 수 있다.

DP[now] = MAX( DP[now-1] , DP[now-2] + DP[now] )

위와 같은 프로그래밍 의사코드로 나타낼 수 있을 것이다.

하지만, 여기서 또 문제바리가 발생한다.

마지막 40위치에서 보자면, 당연히 40과 전전위치의 21을 더한 61이 제일 클 것이다.

그렇지만, 21은 첫 번째 값인 1을 포함한 값이 된다. 마지막과 끝은 연결되어 있으므로,

어찌, 1과 40을 같이 선택할 수 있겠는가?

여기서 원형탐색의 함정이 발생한다.

원형탐색의 시작점을 고려하면, 끝점은 선택하지 못해야한다.
반대로 끝점을 고려하면, 시작점은 선택하지조차 못해야, 이 문제를 해결하는데 있어서 논리적 오류가 발생하지 않는다.

그럼 오히려 물어볼 수 있을 것이다.

첫번째를 고려했더라도, max함수에 의해 두 번째 값보다 작아 선택되지 못하는 경우가 있지 않냐고 말이다.
조금만 쉽게 생각하면, 위와 같은 질문은 우문이 될 것이다.
컴퓨터는 인공지능이 아니다, 여러분들이 작성한 코드 그대로를 가지고, 그냥 처리할 뿐이다.
그렇기에, 물론 첫번째를 고려하더라도 선택되지 않는 경우가 생기겠지만,
그래도 다른 경우에서는 선택되는 경우가 존재하므로,
우리는 시작을 고려하되 마지막을 선택하지 않음, 마지막을 고려하되 시작을 선택하지 않는,
두 가지의 경우로 나누어서 이 문제를 풀어야한다.

[1, 10, 20, 4, 40] 의 원형 배열이 있으면,

[1, 10, 20, 4] 와 [10, 20, 4, 40]으로 분리해서 DP점화식을 적용시켜야 할 것이다.

위의 DP점화식에 전전위치의 계산이 고려된다.

하지만 그렇다고 해서 3번째 위치부터 계산하여 점화식을 적용시켜버리면,

정작 1번째와 2번째 위치를 비교하지 못한다.

그렇기에 배열의 분리된 두 배열에 각각 앞에 0을 추가하여 모든 경우를 고려할 수 있게 하자,

[0, 1, 10, 20, 4] 와 [0, 10, 20, 4, 40]으로 앞에 0을 추가하여 점화식을 적용시키면,

제일 마지막 원소에 우리가 원하는 최곳값을 산출해낼 수 있다.

물론 경우가 2가지로 나누어지므로 각각의 마지막 원소의 최댓값이 정답이 될 테지만.

어렵고 복잡한 글 읽어주셔서 감사하고,

부디 프밍만큼은 포기하지 않기를..