💡 문제 해결 아이디어

내가 생각한 아이디어

• 무작정 하나씩 건너뛰어서 터는 방법은 항상 최댓값을 보장할 수 없다.
  예를 들어, [1, 4, 1, 1, 4, 1]인 경우에는 퐁당퐁당이 아닌 4를 두 번 터는 것(8) 이 베스트이다.
• 새로운 집을 방문했을 때, 도둑이 결정할 수 있는 경우는 딱 3가지이다.
  1. 훔치거나 2. 못 훔치거나 3.안 훔치거나

1. 훔치는 건 그냥 훔치는 것이고
2. 못 훔치는 것은 이전 집에서 훔쳤기에, 어쩔 수 없이 못 훔치는 것이고
3. 안 훔치는 것은 위에 든 예시의 4번째 집처럼 더 큰 이익을 위해 훔칠 수 있지만 안 훔치는 것이다.

그런데, 지금 당장 터는게 이득일지, 안 터는게 이득일지를 그 순간 순간에 판단할 수 없다.
따라서 위 3가지 케이스를 계속해서 업데이트(동적)하면서 마지막에 훔칠 수 있는 최댓값을 반환하는게 맞다.

따라서 이 문제가 DP, 동적계획법으로 분류된 것이다.

🛠 피드백

• 그런데, 이 집들이 원형으로 연결되어 있는 점을 고려할 방법을 생각해내지 못했다.
• "질문하기" 페이지에서 그 힌트를 얻었는데,

1. 첫 집을 털고 마지막 집을 포기하기
2. 첫 집을 포기하고 마지막 집을 털기
   두 경우를 모두 고려하면 된다고 한다.

💻 작성된 코드

def solution(money):
	# 마지막 집을 포기하는 케이스
    rob, cant, no = money[0], 0, 0
    # 첫 집을 포기하는 케이스
    rob2, cant2, no2 = money[1], 0, 0
    
    for i in range(1, len(money)-1):
    	# 훔치려먼 이전에 못/안 훔쳐야한다는 뜻. "둘 중에 더 이익이 큰 루트"를 골라 새로운 이익을 추가
        # 못 훔친다는 것은, "이전에 훔쳤다"는 뜻.
        # 안 훔친다는 것은, "이전에 못 훔쳐서" 이번에는 훔칠 수 있지만, 참는다는 뜻이다.
        rob, cant, no = money[i] + max(cant, no), rob, cant
        rob2, cant2, no2 = money[i+1] + max(cant2, no2), rob2, cant2
    return max(rob, cant, rob2, cant2)

참고로, 두 번 연속으로 "안 훔친다"라는 것은 있을 수 없다. 그것은 손해이다 😂